Recursion in types

The shape of every recursive type

A recursive conditional type has exactly two arms, just like a well-formed recursive function:

• a base case that returns a concrete result without recursing, and
• a recursive case that does a little work and refers to itself on a smaller input.

The “smaller input” is almost always a tuple with its head split off. The real lever is [infer Head, ...infer Tail]. In a conditional type’s extends clause this pattern matches a non-empty tuple, binds the first element to Head and everything after it to Tail. The base case is the empty tuple [], which fails the extends check and falls through to the else arm.

Reverse: the canonical walk

type Reverse<T extends readonly unknown[]> =
  T extends readonly [infer Head, ...infer Tail]
    ? [...Reverse<Tail>, Head]
    : [];

type R = Reverse<[1, 2, 3]>;
//   ^? type R = [3, 2, 1]

Read it as a trace. Reverse<[1,2,3]> matches, Head = 1, Tail = [2,3], so it becomes [...Reverse<[2,3]>, 1]. That recurses to [...Reverse<[3]>, 2, 1], then [...Reverse<[]>, 3, 2, 1], and Reverse<[]> hits the base case []. The accumulated spreads collapse to [3, 2, 1].

Join and Includes — same skeleton, different accumulation

type Join<T extends readonly string[], D extends string> =
  T extends readonly [infer H extends string, ...infer R extends string[]]
    ? R extends [] ? H : `${H}${D}${Join<R, D>}`
    : "";

type J = Join<["a", "b", "c"], "-">;
//   ^? type J = "a-b-c"

type Includes<T extends readonly unknown[], U> =
  T extends readonly [infer H, ...infer R]
    ? [H] extends [U] ? [U] extends [H] ? true : Includes<R, U> : Includes<R, U>
    : false;

type Inc = Includes<[1, 2, 3], 2>;
//   ^? type Inc = true

Join carries the separator D along the recursion and special-cases the last element (R extends []) so the string does not end with a stray delimiter. Includes short-circuits the moment it finds a match — the recursive call only happens in the “not yet found” branch. (Note the [H] extends [U] and [U] extends [H] wrapping — that opts out of distribution so the comparison is exact; you will meet that trick in the next lesson.)

The depth wall — and why tail position matters

When you hit “Type instantiation is excessively deep and possibly infinite.”, the question is whether you have a wrong base case or simply a non-tail call — the same error message covers both, and the fix is different for each. The compiler bounds recursion to keep type checking from hanging. Historically, a recursive conditional type blew up around 50 levels of self-reference with:

type BuildBad<N extends number, Acc extends unknown[] = []> =
  Acc["length"] extends N ? Acc : [unknown, ...BuildBad<N, [unknown, ...Acc]>];
//                                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// Error: Type instantiation is excessively deep and possibly infinite.
// (the recursive call is wrapped in [unknown, ...] — NOT in tail position)

TypeScript 4.5 added tail-recursion elimination on conditional types. When the recursive call is the entire result of a conditional branch — nothing wrapping it — the compiler reuses the evaluation frame instead of nesting, and the effective limit jumps to roughly 1000. The fix is to thread an accumulator and return it directly:

type Build<N extends number, Acc extends unknown[] = []> =
  Acc["length"] extends N
    ? Acc                                     // base case
    : Build<N, [unknown, ...Acc]>;            // TAIL call: the whole branch IS the recursion

type T999 = Build<999>["length"];
//   ^? type T999 = 999   (no error — tail-recursion elimination)

The structural difference: [unknown, ...Build<...>] wraps the call, so each frame must wait for the inner result — not eliminable. Build<N, [unknown, ...Acc]> is the result — eliminable. Restructure your recursion so the self-call sits in tail position and the wall moves from 50 to 1000.