Recursive types
Types that refer to themselves: JSON values and trees, deep transformations like DeepReadonly, the instantiation depth limit, and tail recursion.
Recursive types
The player loads from youtube-nocookie.com when you press play. Nothing reaches YouTube before that.
Not started
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
Why 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.
What 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.
Why 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.
What 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.
You 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
Notes are saved to your account.
Everything else on this page works without one — progress and bookmarks keep themselves in this browser and come with you when you sign in. Notes are the one thing worth not trusting to a browser you might clear.
Your notes could not be loaded.