Recursive types

Advanced · 5 min

Types that refer to themselves: JSON values and trees, deep transformations like DeepReadonly, the instantiation depth limit, and tail recursion.

Before thisConditional typesThe infer keywordMapped types

Warren Day · 5 min

Recursive types

The player loads from youtube-nocookie.com when you press play. Nothing reaches YouTube before that.

Taught by Warren DayReport a problem with this video
Not started
Set this lesson's status

What you'll learn

  • A type can refer to itself as long as the reference sits inside a structure such as an object property, an array element or a tuple, which is how JSON values, trees and nested menus are typed.
  • A recursive conditional type calls itself in one of its branches to repeat a step until a base case is reached, the type-level version of a recursive function.
  • Every recursive conditional needs a base case that stops the recursion, such as an empty tuple, an empty string or a type that is no longer an array.
  • `DeepReadonly` combines a mapped type with recursion to apply `readonly` at every level; it needs a separate case for functions, which would otherwise be mapped into plain objects.
  • TypeScript caps how deeply it will instantiate types; past the cap it reports 'Type instantiation is excessively deep and possibly infinite', and for ordinary recursive conditionals this can happen after only a few dozen levels.
  • Since TypeScript 4.5, a conditional whose branch is nothing but the recursive call is tail-recursive, and the compiler evaluates it in a loop that allows up to about 1,000 iterations.
  • Turning a recursive type into a tail-recursive one usually means adding an accumulator type parameter that carries the partial result, just as with tail-recursive functions.

Data that contains itself

Some data has no fixed depth. A JSON value can be an array of JSON values. A folder holds files and other folders. A comment thread has replies, which have replies. To describe these, a type has to mention itself:

type Json =
  | string
  | number
  | boolean
  | null
  | Json[]
  | { [key: string]: Json };

const config: Json = { name: "app", ports: [80, 443], tls: { enabled: true } };
const notJson: Json = { handler: () => 1 }; // Error: function is not a Json value

interface TreeNode<T> {
  value: T;
  children: TreeNode<T>[];
}

function sum(node: TreeNode<number>): number {
  return node.value + node.children.reduce((total, child) => total + sum(child), 0);
}

The sum function mirrors the type. The type says “a node holds nodes,” and the function says “the sum of a node is its value plus the sums of its nodes.” The recursion in the data and the recursion in the code have the same shape.

A self-reference works when it sits inside some structure: an array element, an object property, a tuple slot. The compiler can expand those lazily, one level at a time, as it checks a value. A type that is nothing but itself has no structure to expand, so it’s rejected:

type Loop = Loop; // Error: Type alias 'Loop' circularly references itself.

Recursive conditional types

The second kind of recursion is in type transformations. A conditional type can use itself in a branch, which repeats a step until it reaches a base case, exactly like a recursive function.

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

type F1 = Flatten<number[][][]>; // number
type F2 = Flatten<string>; // string

Each pass uses infer to peel off one array layer. When T is no longer an array, the false branch returns it, and that’s the base case. Forget the base case, or make it unreachable, and the recursion never stops.

Recursion also combines with mapped types. The built-in Readonly only affects the top level, so nested objects stay writable. A deep version maps every property through itself:

type DeepReadonly<T> = T extends (...args: any[]) => unknown
  ? T
  : T extends object
    ? { readonly [K in keyof T]: DeepReadonly<T[K]> }
    : T;

type Settings = {
  theme: { colors: { primary: string } };
  save: () => void;
};

declare const settings: DeepReadonly<Settings>;
settings.theme.colors.primary = "red"; // Error: Cannot assign to 'primary' because it is a read-only property.
settings.save(); // still callable

The function check comes first because functions are objects too. Without it, save would be mapped into an object type with no call signature, and settings.save() would stop compiling. Arrays need no special case: a mapped type over an array type produces a readonly array.

Strings can recurse as well. This builds on template literal types to pull every parameter out of a route:

type RouteParams<T extends string> =
  T extends `${string}:${infer P}/${infer Rest}`
    ? P | RouteParams<Rest>
    : T extends `${string}:${infer P}`
      ? P
      : never;

type RP = RouteParams<"/users/:id/posts/:postId">; // "id" | "postId"

The depth limit

The compiler can’t tell an infinite type from a very deep one before it finishes, so it gives up past a fixed instantiation depth and reports “Type instantiation is excessively deep and possibly infinite.” For an ordinary recursive conditional, that can happen sooner than you’d expect:

type RepeatSlow<S extends string, N extends number, Count extends unknown[] = []> =
  Count["length"] extends N ? "" : `${S}${RepeatSlow<S, N, [...Count, unknown]>}`;

type Ten = RepeatSlow<"ab", 10>; // "abababababababababab"
type Sixty = RepeatSlow<"a", 60>; // Error: Type instantiation is excessively deep and possibly infinite.

The Count tuple is the usual trick for counting at the type level, since you can’t do arithmetic on number types directly but can read a tuple’s length. The exact point of failure depends on how much work each level does. It’s often somewhere between a few dozen and around a hundred levels.

Tail recursion

TypeScript 4.5 added a way past this. If a branch of a conditional is only the recursive call, with nothing wrapped around it, the compiler treats it as a tail call. It evaluates it in a loop instead of nesting, and allows up to about 1,000 iterations.

RepeatSlow isn’t tail-recursive, because its recursive call is wrapped in a template string that still has work to do afterwards. Moving that work into an accumulator parameter fixes it:

type Repeat<
  S extends string,
  N extends number,
  Count extends unknown[] = [],
  Acc extends string = "",
> = Count["length"] extends N ? Acc : Repeat<S, N, [...Count, unknown], `${Acc}${S}`>;

type Long = Repeat<"a", 500>; // fine, a 500-character string literal

Think of carrying a running total on a receipt instead of keeping every step in your head. The non-tail version has to remember “and then prepend S” at every level until the bottom is reached. The tail version writes the partial result into Acc and forgets the step.

The same rewrite applies to any recursive type: add an accumulator, build the result in it, and return it in the base case. Recursion this deep is rare in application code, but library types that parse strings or walk long tuples depend on it.

About the video

Warren Day’s video is under five minutes and works through three examples showing the main ways to write recursive types, covering both self-referencing data shapes and recursive transformations. It’s a quick introduction to the first two sections above. The depth limit and tail recursion aren’t part of it, which is why this lesson covers them in detail. For more practice, the Typed Rocks video linked below uses recursion to replace property types throughout deeply nested objects, and Simon’s talk builds recursive template literal types that type dotted paths into nested objects.

Check yourself

  1. 01Why is `type Json = string | number | boolean | null | Json[] | { [key: string]: Json }` allowed when `type Loop = Loop` is not?

    In `Json`, each self-reference is inside an array or object type, so the compiler can expand it lazily, one level at a time, as values are checked. `type Loop = Loop` says nothing except that the type is itself, so there is no structure to expand and it is reported as circular.

  2. 02What does `Flatten<number[][][]>` resolve to, given `type Flatten<T> = T extends readonly (infer E)[] ? Flatten<E> : T`?

    `number`. Each step strips one array layer: `number[][][]` to `number[][]` to `number[]` to `number`. `number` isn't an array, so the false branch, the base case, returns it unchanged.

  3. 03Why does a `DeepReadonly` type usually check for functions before mapping over objects?

    Functions are objects, so without a separate case the mapped type would map over a function's properties and produce a plain object type that is no longer callable. Returning function types unchanged keeps methods callable.

  4. 04What is the difference between `[...Reverse<R>, H]` and `ReverseAcc<R, [H, ...Acc]>` as the recursive branch of a conditional type?

    The first wraps the recursive call in more work, a tuple spread, so it is not a tail call and runs into the instantiation depth limit after a modest number of levels. The second is just the recursive call, with the partial result passed along in an accumulator, so since TypeScript 4.5 it is evaluated as a tail call and can run for about 1,000 iterations.

  5. 05You see 'Type instantiation is excessively deep and possibly infinite' on a recursive type. What are your options?

    Check that the base case is reachable for the input. If it is, the input may just be too large; rewrite the type to be tail-recursive with an accumulator, reduce the work per level, or accept the limit and type very large inputs more loosely, for example as `string`.

Go deeper

Notes

Private to you

Esc
↑↓ navigate↵ open? shortcuts

Keyboard shortcuts

Press Esc to close

Anywhere

⌘K
Search and commands
/
Search
?
This sheet
Esc
Close

Reading a lesson

J
Next lesson
K
Previous lesson
B
Bookmark