Tail Recursive Generics

Detection

Watch for these symptoms:

// ERROR: Type instantiation is excessively deep
type DeepTransform<T> = T extends object
  ? { [K in keyof T]: DeepTransform<T[K]> }
  : T;

// Works for shallow objects, fails for deeply nested ones
type Test = DeepTransform<{ a: { b: { c: { d: { e: string } } } } }>;

The Problem: Non-Tail Recursion

// BAD: Non-tail-recursive - builds nested type structure
type NTuple<T, N extends number> = 
  N extends 0 
    ? []
    : [T, ...NTuple<T, Subtract<N, 1>>];
//          ^^^^^^^^^^^^^^^^^^^^^^^^^^
//          Recursive call not in tail position
//          TypeScript can't optimize this

// Each recursive call adds a layer:
// NTuple<T, 3> = [T, ...NTuple<T, 2>]
//              = [T, ...[T, ...NTuple<T, 1>]]
//              = [T, ...[T, ...[T, ...[]]]]
// Depth grows with N

The Solution: Tail Recursion with Accumulator

// GOOD: Tail-recursive with accumulator
type NTuple<T, N extends number> = NTupleHelp<T, N, []>;

type NTupleHelp<T, N extends number, Acc extends T[]> =
  Acc['length'] extends N
    ? Acc
    : NTupleHelp<T, N, [T, ...Acc]>;
//    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//    Recursive call is in tail position
//    TypeScript can optimize this

// Accumulator builds result iteratively:
// NTupleHelp<T, 3, []>
// → NTupleHelp<T, 3, [T]>
// → NTupleHelp<T, 3, [T, T]>  
// → NTupleHelp<T, 3, [T, T, T]>
// → [T, T, T] (Acc['length'] extends 3)

Real-World Example: Deep Readonly

// BAD: Non-tail-recursive, hits depth limit
type DeepReadonly<T> = T extends object
  ? { readonly [K in keyof T]: DeepReadonly<T[K]> }
  : T;

// GOOD: Tail-recursive with accumulator
type DeepReadonly<T> = DeepReadonlyHelp<T, []>;

type DeepReadonlyHelp<T, Seen extends unknown[]> = 
  T extends object
    ? T extends Seen[number]  // Check for circular reference
      ? T
      : { 
          readonly [K in keyof T]: DeepReadonlyHelp<
            T[K], 
            [T, ...Seen]  // Accumulate seen types
          > 
        }
    : T;

// Usage
type Deep = DeepReadonly<{
  a: { b: { c: { d: { e: { f: string } } } } }
}>;
// Works without hitting depth limit!

String Transformation Example

// BAD: Non-tail-recursive string replacement
type ReplaceAll<S extends string, From extends string, To extends string> =
  S extends `${infer Before}${From}${infer After}`
    ? `${Before}${To}${ReplaceAll<After, From, To>}`  // Not tail-recursive
    : S;

// GOOD: Tail-recursive with accumulator
type ReplaceAll<S extends string, From extends string, To extends string> =
  ReplaceAllHelp<S, From, To, ''>;

type ReplaceAllHelp<
  S extends string,
  From extends string,
  To extends string,
  Acc extends string
> = S extends `${infer Before}${From}${infer After}`
  ? ReplaceAllHelp<After, From, To, `${Acc}${Before}${To}`>
  : `${Acc}${S}`;

// Usage
type Result = ReplaceAll<'foo-bar-baz', '-', '_'>;
// 'foo_bar_baz' - works for long strings!

Key Principles

// 1. Pass accumulator as type parameter
type Transform<T, Acc = []> = /* ... */;

// 2. Recursive call must be in tail position
// BAD:  [T, ...Recursive<...]  // Spread is not tail position
// GOOD: Recursive<..., [...Acc, T]>  // Accumulator updated

// 3. Base case checks accumulator
type Helper<T, Acc> = Condition<Acc> extends true
  ? Acc  // Return accumulated result
  : Helper<T, Update<Acc>>;  // Continue with updated accumulator

When Tail Recursion Doesn't Help

Some types are inherently deep:

// Pathological case: deeply nested object
type Deep = {
  a: { b: { c: { d: { e: { f: { g: string } } } } } }
};

// Even tail-recursive types may struggle with
// objects nested 50+ levels deep

Pressure Resistance Protocol

When hitting depth limit errors:

1. Identify recursion: Find the recursive type causing issues
2. Add accumulator: Create helper type with accumulator parameter
3. Move to tail position: Ensure recursive call is last operation
4. Test with deep cases: Verify it handles deeply nested types
5. Consider alternatives: Sometimes runtime validation is better

Red Flags

Common Rationalizations

"I'll just increase TypeScript's depth limit"

Reality: There's no configuration for this. The limit protects against infinite loops.

"My types aren't that deep"

Reality: Generated types (from GraphQL, etc.) can be deeper than expected. Tail recursion makes them robust.

"This is too complex"

Reality: The pattern is simple: helper type + accumulator. Learn it once, apply everywhere.

Quick Reference

The Bottom Line

Use accumulator patterns to make recursive generic types tail-recursive. This avoids "excessively deep" errors and makes your types work with arbitrarily large inputs.

Reference

• Effective TypeScript, 2nd Edition by Dan Vanderkam
• Item 57: Prefer Tail-Recursive Generic Types