Skip to content
Tutorials Center
My learning

Topics

Lesson 47 of 96 ยท Type Manipulation

Recursive Types

Learn TypeScript recursive types - self-referencing aliases for trees and JSON, recursive conditional and mapped types like DeepReadonly and Flatten, and depth limits.

Some data is naturally self-similar. A folder contains files and other folders. A comment has replies, and each reply can have replies. A JSON value can be an array of JSON values. To describe such data, a type has to refer to itself, and TypeScript supports that: a type can mention its own name in its definition, as long as the mention sits somewhere the compiler can defer.

This lesson starts with recursive object types and trees, then builds the JSON type, then moves to the more powerful form: recursive conditional types and mapped types that walk through a type and transform every level, such as DeepReadonly<T> or Flatten<T>. It closes with the limits of recursion and how to stay inside them. You should be comfortable with generics, keyof and infer from the conditional types lesson.

Self-referencing object types

The simplest recursive type is an object with a property of its own type. A linked list node is the classic example:

TypeScript
interface ListNode<T> {
  value: T;
  next: ListNode<T> | null;
}

This works because the reference is inside an object property. TypeScript does not need to expand ListNode<T> right away to know what the type is; it can look inside it later, when you actually access .next. The same is true for arrays and function types: a reference inside Item[], inside a tuple, or inside a function signature is deferred.

TypeScript A tree type and a recursive function over it

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or readFileSync(0)), it gets the next line from this box.

The type is recursive and so are the functions. That is the usual pairing: the shape of a recursive function follows the shape of the recursive type. render handles one node and calls itself for each child, and TypeScript knows child is again a TreeNode<T>. The output is the indented list of six roles, followed by nodes: 6 height: 4.

flowchart TD
    CEO --> CTO
    CEO --> CFO
    CTO --> DL["Dev lead"]
    CTO --> OL["Ops lead"]
    DL --> Dev["Developer"]

The tree from the example. Every box has the same type, TreeNode of string.

Recursion in type aliases

Interfaces have always allowed self-reference. Type aliases are a little pickier. This one is fine, because the reference hides inside an array:

TypeScript
type Nested<T> = T | Nested<T>[];

const ok: Nested<number> = [1, [2, [3, [4]]]];

Older TypeScript versions rejected that with "Type alias circularly references itself". Modern versions accept it as long as the recursive mention is inside an object, array, tuple or function type. What is still an error is a direct, unguarded loop:

TypeScript
type Broken = Broken | string;   // error TS2456: Type alias 'Broken' circularly references itself

There is no structure to defer, so the compiler cannot even decide what Broken means. The rule of thumb: put the recursion inside a property, an array or a tuple.

The JSON type

A classic use of a recursive alias is a type for any value that JSON.parse can return:

TypeScript A JsonValue type and a depth function

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or readFileSync(0)), it gets the next line from this box.

JsonValue appears in two recursive positions: inside the array and in the index signature. The function depth branches on typeof value === 'object' and the Array.isArray check narrows the union so each branch sees the right type. The program prints depth: 3 and then the seven leaf paths, from .name to .active.

Recursive conditional types

Conditional types can call themselves. This lets a type walk through nested structures one step at a time. The most common building block is infer, which captures a piece of the type so the recursion can continue with it.

A first example is Flatten<T>, which unwraps any depth of array nesting:

TypeScript
type Flatten<T> = T extends readonly (infer Item)[] ? Flatten<Item> : T;

type A = Flatten<number[][][]>;           // number
type B = Flatten<(string | number[])[]>;  // string | number
type C = Flatten<boolean>;                // boolean

Read it like a recursive function: "if T is an array of Item, the answer is Flatten<Item>; otherwise the answer is T itself". The base case is the : T branch. Because the conditional is distributive, the union in B is processed member by member.

Here is a second one that works on tuples: reversing and measuring.

TypeScript Recursive conditional types, checked at compile time

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or readFileSync(0)), it gets the next line from this box.

The three assertType calls are checked by the compiler and erased from the output; if you change an expected type to a wrong one, you get an error right on that line. The program prints [ false, 'x', 1 ] deep and type checks passed. This "type test" style is how library authors test their types, and you will meet it again in Type-Level Programming.

Recursive mapped types

A mapped type can apply itself to each property, which gives you the "deep" versions of the standard utilities. Utility Types gave you Partial<T> and Readonly<T>, which only touch the top level. The deep versions recurse into objects:

TypeScript DeepReadonly and DeepPartial

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or readFileSync(0)), it gets the next line from this box.

Two details matter. First, the function check comes first: without it, a function property would be treated as an object and mapped over its (empty) keys, which loses its call signature. Second, arrays and tuples are objects too, and mapped types over arrays preserve their array-ness, so DeepReadonly<string[]> becomes readonly string[], which is why push is rejected in the commented line. The program prints localhost:8080 tls=false, then localhost:8080 tls=true, then [log] done.

Note that these simple versions treat Date, Map and Set as plain objects, so their methods get mapped over as well. Real libraries add special cases for such types, or you can add a branch such as T extends Date | RegExp ? T : where you need it.

Recursive paths: a string-building example

Template literal types combine nicely with recursion. Here is a type that lists every dotted path into an object, which powers helpers like get(obj, 'server.tls.enabled'):

TypeScript
type Paths<T> = T extends object
  ? { [K in keyof T & string]: T[K] extends object ? K | `${K}.${Paths<T[K]>}` : K }[keyof T & string]
  : never;

interface Settings { theme: string; editor: { tabSize: number; wrap: boolean } }

type SettingsPath = Paths<Settings>;
// "theme" | "editor" | "editor.tabSize" | "editor.wrap"

The mapped type produces an object whose values are the path strings, and indexing it by keyof T & string collapses the object into a union. See Template Literal Types for the string tools used here.

Limits and how to stay inside them

Recursive types are evaluated by the compiler, and the compiler protects itself:

  • Depth limit. If a type needs more than roughly a hundred nested instantiations, you get error TS2589, "Type instantiation is excessively deep and possibly infinite". Self-referencing data (an arbitrary JsonValue) is not affected, because it is only expanded as deep as the values you actually write.
  • Tail recursion. Since TypeScript 4.5, a conditional type that calls itself as the last thing in a branch is optimized, and can recurse about a thousand times. To use this, carry the result in an accumulator parameter instead of wrapping the recursive call in more type syntax.
  • Cost. Every deep type has to be computed for every use. A DeepPartial on a huge generated API type can slow your editor noticeably. Prefer simple, shallow types in hot paths.
  • Unions explode. Recursive types over big unions can produce thousands of members. Keep the inputs small.

Here is the accumulator style, which is the one to use for long inputs:

TypeScript
// Not tail recursive: the recursive call is wrapped in a tuple.
type ReverseSlow<T extends unknown[]> =
  T extends [infer H, ...infer R] ? [...ReverseSlow<R>, H] : [];

// Tail recursive: the call is the whole branch, and the result travels in Acc.
type ReverseFast<T extends unknown[], Acc extends unknown[] = []> =
  T extends [infer H, ...infer R] ? ReverseFast<R, [H, ...Acc]> : Acc;

When a recursive type gets hard to read, write the matching recursive function first, with the same base case and the same step, then translate it into types. The two have the same shape.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which recursive alias is rejected by TypeScript?

    A direct loop with nothing in between (no object, array, tuple or function) cannot be resolved (TS2456). The other three put the self-reference inside a structure the compiler can defer.
  2. 2. What is Flatten<string[][]> with type Flatten<T> = T extends readonly (infer I)[] ? Flatten<I> : T?

    Each step unwraps one array level until T is no longer an array, and the base case returns string.
  3. 3. Why does DeepReadonly check for function types before objects?

    A function is an object type, so the object branch would also match it. Mapping over its keys would produce an empty-looking object and lose the call signature.
  4. 4. What makes a recursive conditional type eligible for the tail-recursion optimization?

    When the recursive call is the entire result of a branch, the compiler can loop instead of nesting, which raises the limit to about a thousand steps.
  5. 5. What does Paths<{ a: { b: number } }> (the Paths type above) produce?

    Object properties contribute both their own name and the dotted paths below them, so the result is a union of "a" and "a.b".

Summary

  • A type may refer to itself when the reference sits inside an object property, array, tuple or function type; a bare self-loop like type Bad = Bad | string is an error.
  • Recursive data types such as trees and JsonValue pair naturally with recursive functions that follow the same shape.
  • Recursive conditional types use infer and a base case, like Flatten, Reverse and Last, and can be checked with small compile-time assertions.
  • Recursive mapped types give deep versions of the utilities: DeepReadonly, DeepPartial. Handle functions (and special objects such as Date) explicitly.
  • The compiler limits recursion depth (TS2589); tail-recursive forms with an accumulator go much further.
  • Keep recursive types simple and shallow where they are used often, since they cost compile time.

Next: Modules