tail-recursive-generics

优先使用尾递归泛型

概述

TypeScript 会限制类型实例化的深度，以防止无限循环。当遇到“Type instantiation is excessively deep and possibly infinite”（类型实例化过深，可能是无限的）错误时，你需要重构递归类型，使其变为尾递归。使用累加器模式，可以编写 TypeScript 能够优化的类型，避免触及深度限制。

对于处理大型或深度嵌套结构的类型级编程，这项技巧至关重要。

何时使用此技巧

• 遇到“Type instantiation is excessively deep”错误
• 编写递归泛型类型
• 处理大型类型结构
• 构建类型级循环或迭代
• 转换深度嵌套的对象

铁律

使用累加器模式使泛型类型成为尾递归。将累积结果作为类型参数传递，而不是构建嵌套的类型结构。

检测

留意以下症状：

// 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 } } } } }>;

问题：非尾递归

// 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

解决方案：使用累加器进行尾递归

// 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)

实际示例：深度只读

// 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!

字符串转换示例

// 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!

核心原则

// 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

尾递归无济于事的情况

有些类型本身就很深：

// 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

抗压应对流程

遇到深度限制错误时：

1. 识别递归：找到导致问题的递归类型
2. 添加累加器：创建带有累加器参数的辅助类型
3. 将递归调用移至末尾：确保递归调用是最后一个操作
4. 使用深层案例测试：验证它能处理深度嵌套类型
5. 考虑替代方案：有时运行时验证更合适

危险信号

反模式	问题	解决方案
元组中的 ...Recursive<...>	不是尾递归	使用累加器
没有累加器的深度嵌套	触及深度限制	添加累加器参数
条件中的递归调用	可能无法优化	重构

常见借口

“我只要提高 TypeScript 的深度限制就行”

事实：没有针对这一点的配置。此限制用于防止无限循环。

“我的类型没那么深”

事实：生成的类型（例如来自 GraphQL 的类型）可能比预期更深。尾递归能让它们更稳健。

“这太复杂了”

事实：这个模式很简单：辅助类型 + 累加器。学会一次，到处应用。

快速参考

模式	非尾递归	尾递归
构建元组	[T, ...Rec<N-1>]	Rec<N, [T, ...Acc]>
构建字符串	`${X}${Rec<Y>}`	`Rec<Y, `${Acc}${X}`>`
遍历对象	{ [K]: Rec<T[K]> }	Rec<T[K], [T, ...Acc]>

总结

使用累加器模式使递归泛型类型成为尾递归。这可以避免“过深”错误，并让类型能够处理任意大的输入。

参考资料

• Dan Vanderkam 著《Effective TypeScript》第 2 版
• 条目 57：优先使用尾递归泛型