如何突破TypeScript尾递归次数限制并兼顾性能？

在TypeScript类型体操中，传统元组计数（如NumToTuple）依赖线性递归，受限于TS的尾递归优化上限（通常默认约1000次）；而NumToBigTuple这类线性扩展方案会因递归次数暴增导致性能急剧下降。要解决这个问题，核心思路是用二进制分治替代线性递归，将计数复杂度从O(N)降到O(log₂N)，大幅减少递归次数，提升性能。

核心实现思路 #

把目标数字拆分为二进制幂次的组合（比如13=8+4+1，对应2³+2²+2⁰），先通过递归翻倍快速生成各幂次对应的元组（长度为2ⁿ的元组仅需n次递归），最后将这些幂次元组合并为总长度的元组。

具体代码实现 #

// 辅助类型：判断两个类型是否相等
type Equals<A, B> = 
  (<T>() => T extends A ? 1 : 2) extends 
  (<T>() => T extends B ? 1 : 2) ? true : false;

// 生成长度为2^n的元组，递归次数为log₂(2^n)=n次
type Pow2Tuple<N extends number, R extends unknown[] = []> = 
  Equals<R['length'], N> extends true ? R : Pow2Tuple<N, [...R, ...R]>;

// 将数字拆分为二进制幂次的数组（例如13 → [8,4,1]）
type SplitNumber<
  N extends number,
  CurrentPow extends number = 1,
  Result extends number[] = []
> = 
  N extends 0 
    ? Result
    : N extends CurrentPow
      ? [...Result, CurrentPow]
      : N extends infer U extends number
        ? U < CurrentPow
          ? SplitNumber<N, CurrentPow extends 1 ? 2 : CurrentPow extends 2 ? 4 : CurrentPow extends 4 ? 8 : CurrentPow extends 8 ? 16 : never, Result>
          : SplitNumber<N - CurrentPow, CurrentPow * 2, [...Result, CurrentPow]>
        : never;

// 合并多个幂次元组，得到目标长度的元组
type CombineTuples<T extends number[], R extends unknown[] = []> = 
  T extends [infer First extends number, ...infer Rest extends number[]]
    ? CombineTuples<Rest, [...R, ...Pow2Tuple<First>]>
    : R;

// 最终的高性能数字转元组类型
type NumToFastTuple<N extends number> = 
  CombineTuples<SplitNumber<N>>;

性能优势说明 #

• 递归次数呈对数级增长：比如生成长度为10000的元组，仅需约14次递归（因为2¹⁴=16384），远低于线性递归的10000次，完全不会触发TS的递归深度限制。
• 内存占用更高效：幂次元组通过翻倍复制生成，比逐个push元素的线性递归更节省类型系统的内存开销。

注意事项 #

• TS类型系统对超大数字（如百万级）的运算仍有一定限制，但该方案支持的数值上限远高于线性递归方案。
• 可根据需求优化SplitNumber中的幂次枚举逻辑，比如扩展支持更高的初始幂次，减少拆分步骤。

内容的提问来源于stack exchange，提问作者Autumn