Suggest an edit

Improve this article

Refine the answer for “Recursive type”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## 1) A basic generic tree node

```javascript
interface TreeNode<T> {
  id: string;
  value: T;
  children?: TreeNode<T>[]; // recursion: a node holds a list of the same kind of nodes
}

const tree: TreeNode<number> = {
  id: "root",
  value: 0,
  children: [
    { id: "a", value: 1 },
    { id: "b", value: 2, children: [{ id: "b1", value: 3 }] },
  ],
};
```

> `interface` and `type` work equally well for recursion; pick whichever fits your project's style.

---

## 2) A discriminated union (a stricter "leaf/branch" mode)

```javascript
type Leaf<T> = {
  kind: "leaf";
  id: string;
  value: T;
};

type Branch<T> = {
  kind: "branch";
  id: string;
  value: T;
  children: Tree<T>[]; // recursive
};

type Tree<T> = Leaf<T> | Branch<T>;

const t: Tree<string> = {
  kind: "branch",
  id: "root",
  value: "root",
  children: [{ kind: "leaf", id: "l1", value: "x" }],
};
```

> This approach prevents "leaves with children" or "branches without children".

---

## 3) A "dictionary" tree (key → subtree)

```javascript
type DictTree<T> = {
  value?: T;
  children?: Record<string, DictTree<T>>; // recursion through Record
};

const categories: DictTree<null> = {
  children: {
    clothes: {
      children: { shirts: { value: null }, pants: { value: null } },
    },
  },
};
```

---

## 4) Links upward (parent) - be careful with circular references

```javascript
interface LinkedNode<T> {
  id: string;
  value: T;
  parent?: LinkedNode<T>;         // up
  children?: LinkedNode<T>[];     // down
}
```

> Such structures are inconvenient to serialize to JSON (cycles). In a DTO you usually store `parentId: string` instead of `parent`.

---

## 5) Traversal/utilities with precise typing

```javascript
function traverse<T>(node: TreeNode<T>, visit: (n: TreeNode<T>) => void) {
  visit(node);
  node.children?.forEach(child => traverse(child, visit));
}

function mapTree<A, B>(node: TreeNode<A>, f: (v: A) => B): TreeNode<B> {
  return {
    id: node.id,
    value: f(node.value),
    children: node.children?.map(c => mapTree(c, f)),
  };
}
```

---

## 6) Recursive utilities (DeepReadonly / DeepPartial)

```javascript
type DeepReadonly<T> = {
  readonly [K in keyof T]: DeepReadonly<T[K]>;
};

type DeepPartial<T> = {
  [K in keyof T]?: DeepPartial<T[K]>;
};
```

Usage:

```javascript
type FrozenTree<T> = DeepReadonly<TreeNode<T>>;
type PatchTree<T>  = DeepPartial<TreeNode<T>>;
```

---

## 7) A type for "a nested object of arbitrary depth"

```javascript
type Nested<T> = T | { [key: string]: Nested<T> };

const i18n: Nested<string> = {
  app: { title: "Shop", nav: { home: "Home" } },
};
```

---

## 8) On "too deep" types

If you get an error like *"type instantiation is excessively deep and possibly infinite"* in heavily recursive **mapped types**, split it into levels (a Depth parameter) or simplify the branches (for example, stop at arrays or primitives).

An example of limiting the depth:

```javascript
type Dec<N extends number> = [
  never, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
][N]; // a primitive decrement for 0..9

type DeepReadonlyN<T, N extends number = 5> =
  N extends 0 ? T :
  T extends object
    ? { readonly [K in keyof T]: DeepReadonlyN<T[K], Dec<N>> }
    : T;
```

---

## Summary

- Recursion works in both `interface` and `type`.
- For a strict tree model, **discriminated unions** are convenient.
- For dictionaries - `Record<string, RecType>`.
- For serialization, avoid bidirectional references; use `parentId`.
- For "deep" utilities, use `DeepReadonly/DeepPartial` or limit the depth.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts536 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.