PHASE 9Advanced ~27 min· topic 5 of 5

Topic 9.5

Recursive Types

In one line

A recursive type refers to itself, so it can describe data of any depth (JSON, nested configs) and can loop over strings and tuples, as long as it stays inside the compiler's depth limits.

Think of it like this

Russian nesting dolls. Open one doll and inside is another doll, which has another inside, until you reach a solid one at the bottom. A recursive type is a nesting doll: its definition mentions itself, and it stops when it reaches a case that does not. A folder can hold files or other folders, and each of those folders can hold more: that's a recursive shape, and a recursive type describes it.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Recursive type: A type whose definition uses the type itself, like Json containing Json[].
Base case: The branch that stops the recursion because it does not refer back to the type.
Deep (operation): Applied at every level of nesting, not just the top.
Tail-recursive: The recursive call is the entire result of the branch, so nothing waits to be done after it returns.
Accumulator: An extra type parameter that carries the answer built so far through each step.
Instantiation depth: How many nested type evaluations the compiler is inside. It stops at a limit.
TS2589: The error Type instantiation is excessively deep and possibly infinite: the safety limit was hit.

Step by step

01A type that names itself

Json is a union where two members mention Json again: an array of Json, and an object whose values are Json.

Any depth of nesting is accepted. A Date fails: the error ends with Index signature for type 'string' is missing in type 'Date', because a Date is not a plain dictionary.

json.tswhole filets

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

const ok: Json = { name: "Asha", tags: ["a", "b"], spare: null };
const bad: Json = { birthday: new Date() }; // error TS2322

02Apply a change at every level

DeepReadonly checks three cases in order: a function (leave it), an object (map over its keys and recurse), anything else (leave it).

The mapped type makes each property readonly and calls DeepReadonly on the property type. When the property is itself an object or an array, the same happens one level lower.

Apply a change at every leveldiagram

Rendering diagram…

03Loop over a string

Reverse<S, Acc> takes the first character off, adds it to the front of Acc, and calls itself on the rest. When no character is left, the answer is Acc.

The recursive call is the whole branch, so this is a tail call and the compiler turns it into a loop.

reverse.tswhole filets

type Reverse<S extends string, Acc extends string = ""> =
  S extends `${infer H}${infer T}` ? Reverse<T, `${H}${Acc}`> : Acc;

type Rev = Reverse<"hello">; // "olleh"

04Count with a tuple, then hit the wall on purpose

Types cannot do i++, so a counter is a tuple that grows by one item per step. In Build<N, Acc>, Acc is the tuple built so far (it starts as []), [...Acc, unknown] is a copy with one more item (Topic 5.2, spread in tuples), and Acc["length"] is how many items it has. When the length equals N the loop stops and returns Acc.

This counter works until 999 steps. At 1000 or more the compiler says TS2589 and the result is any. TypeScript 6.0 and 7.0 stop at the same place.

A recursive type that adds text *around* the recursive call is not a tail call and stops far earlier: with the Repeat type in the third live example, 47 steps work and 48 fail, in both 6.0 and 7.0. Add an accumulator, and the limit goes back to 999.

build.tswhole filets

type Build<N extends number, Acc extends unknown[] = []> =
  Acc["length"] extends N ? Acc : Build<N, [...Acc, unknown]>;

type Three = Build<3>["length"]; // 3 (Acc grows [] → [unknown] → [unknown, unknown] → ...)

Try it yourself

1
Find the edge
Change Build<900> to Build<999> and then Build<1000>. In our test 999 worked and 1000 gave TS2589 and the type any.
2
Deep readonly for arrays of objects
Add users: { name: string }[] to Config. Predict whether config.users[0].name = "x" is rejected. It is, with TS2540 (read-only property). You will also see TS2532: Object is possibly 'undefined' on the same line, because this course's editor has noUncheckedIndexedAccess on (Topic 1.4): indexing an array may give undefined. Then try config.users.push({ name: "y" }) and read the TS2339 error: the array became readonly, so push is gone.
3
Allow nested arrays in Json
Add [1, [2, [3]]] as a Json value. It's accepted: the base cases of Json are the primitives, the rest recurse.

Code & diagrams

JSON as a recursive type

Deep inside the error message, TypeScript walks down the nesting to the exact property that does not fit (birthday, then run).

Console

(nothing was printed)

Expected console output

{"name":"Asha","tags":["a","b"],"address":{"city":"Pune","pin":411001},"spare":null}

Deep readonly and deep partial

Three writes are rejected at three different depths. Look at ports in Patch: DeepPartial made the array items possibly undefined, a known side effect.

Console

(nothing was printed)

Expected console output

{ server: { ports: [ 8080 ] } }

Recursion limits and tail-recursive types

Repeat wraps text around its recursive call, so 50 steps already fails (45 still works). Build is tail-recursive and reaches 900, but 2000 fails.

Console

(nothing was printed)

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Count past the limit

In the third example, type TooMany = Build<2000>["length"] asks the tail-recursive counter for 2000 steps.

terminal

$ Types panel

── what you'll see ──

index.ts(16,16): error TS2589: Type instantiation is excessively deep and possibly infinite.

Myth vs fact

Myth

TS2589 means my type is wrong.

Fact

It means the type went deeper than the compiler allows. The type may be correct for small inputs.

Myth

A recursive type alias is not allowed.

Fact

Recursion is allowed when the self-reference sits inside an object, array or conditional type, like Json[] or Tree<T>[]. Only an alias that needs itself right away to be defined is rejected, with TS2456: Type alias 'A' circularly references itself: type A = A and type C = C | string both are.

Myth

DeepPartial is safe for every type.

Fact

On arrays it makes items T | undefined, and on classes, maps and dates it can break their methods. Handle those cases explicitly if you need them.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
Tail-call elimination for conditional types arrived in TypeScript 4.5. The compiler loops while the branch returns another instantiation of the same alias, with a cap of 1000 iterations (the 6.0 compiler source checks tailCount === 1e3, and our runs show 7.0 stops at the same count). Without it the limit is a nesting depth of about 100 instantiations, which is why a non-tail Repeat fails after a few dozen steps.
▸
The error message gives the line of the *use*, not the line of the definition. If the failing line is far away, look for what you passed in: usually an unexpectedly huge union or a number that is too large.
▸
Because JSON.stringify skips undefined and functions and turns Date into a string, the Json type models the data after parsing, not every value JSON.stringify accepts. Use it at the boundary where parsed data enters your program (Topic 13.4).

Remember this

1
The problem this solves: some data has no fixed depth. A folder holds folders, a comment has replies that have replies, JSON can nest as deep as it likes. A type written out level by level would stop at some level. A recursive type describes every depth with one definition. Some type-level work needs the same trick: looping over the characters of a string, or counting. Types have no for loop, so a type calls itself instead.
2
The simplest case is a recursive type alias for data. JSON is: a string, number, boolean, null, an array of JSON, or an object whose values are JSON. In TypeScript: ` type Json = string | number | boolean | null | Json[] | { [key: string]: Json } . The type names itself inside its own definition, and that works because arrays and objects can be described lazily. A Date or a function is rejected, because neither is JSON (JSON.stringify` would drop or change them).
3
Deep readonly and deep partial apply a change at every level. Recall from Topic 8.4: a mapped type { readonly [K in keyof T]: ... } rebuilds an object type key by key, but only one level deep. DeepReadonly<T> says: leave functions alone; for objects, make every property readonly and apply DeepReadonly to each property type; anything else is left as it is. Because readonly on a mapped type over an array makes a readonly array, even push disappears. DeepPartial<T> does the same with ?. Note that DeepPartial on an array makes the items possibly undefined, shown as (number | undefined)[], which is often not what you want.
4
Recursion in conditional types lets a type loop (Topic 9.1 conditional types, Topic 9.3 infer, Topic 9.4 taking strings apart). Split<S, D> from Topic 9.4 calls itself on the rest of the string, Reverse<S> on the tail. A loop needs a base case (the branch that does not call itself). Without one, the compiler would never finish, so it gives up with an error.
5
The compiler has limits. Each time a type calls itself, a counter goes up. When a type is instantiated too deep, TypeScript stops with TS2589: Type instantiation is excessively deep and possibly infinite. This is the compiler's safety net, not a bug in your type: its job is to stop a runaway type from freezing your editor.
6
Tail-recursive conditional types (the recursive call is the whole answer of a branch, passed an accumulator) are optimised into a loop and can run about a thousand times. Building a counter with Build<N, Acc> works up to 999. A type that does something *after* the recursive call returns (like ${S}${Repeat<...>}) is not a tail call, and fails after a few dozen steps. The fix is an accumulator parameter: carry the answer so far in an extra parameter, as Reverse<T, ${H}${Acc}> does.
7
Use recursion when the data is truly recursive (trees, JSON, paths). When a type has to count high, rewrite it with an accumulator. And be honest about cost: a clever recursive type slows the editor for everyone. Topic 10.6 helps you decide when to stop.

Explain it without notes

What is a recursive type? Give an example.

Why does Repeat fail at 50 steps but Build works up to 900?

What does TS2589 mean and what can you do about it?

What does DeepReadonly do to an array property?

Practice

Write type Tree<T> = ... for a tree node with a value and an array of child trees, then create a tree of three nodes.

Write Flat<T> that flattens any depth of arrays: Flat<number[][][]> is number.

Write Length<S> that counts the characters of a string type with an accumulator tuple.

Trade-offs

↔
Recursive types describe real nested data exactly. The price is compile time and the depth limit, plus error messages that are hard to read. Keep them small and named.

Done when you can

I can write a recursive type alias such as Json.
I can write DeepReadonly and explain each branch.
I can tell a tail-recursive conditional type from a non-tail one.
I can read TS2589 and name two ways to fix it.
I can use an accumulator parameter.

Command Palette

Words you'll meet

Step by step

01A type that names itself

02Apply a change at every level

03Loop over a string

04Count with a tuple, then hit the wall on purpose

Try it yourself

Find the edge

Deep readonly for arrays of objects

Allow nested arrays in Json

Code & diagrams

Break it on purpose

Count past the limit

Myth vs fact

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can