# 冷门-递归深度

相信大家在做 ts 类型体操的过程中，偶尔会碰到 Type instantiation is excessively deep and possibly infinite.ts(2589) 这个告警，往往比较懵逼，而且网上关于这一部分的讨论，其实也不多。

绝大部分文章会告诉你，递归深度控制在 50 以内，就不会有这个问题，但是实际情况中，往往有时候我们的递归深度可以超过 50，达到 999，也不会触发这个问题，直到达到 1000。

本文便是对这一问题的解惑。

# 问题复现

我们以计算字符的长度问题为例，复现这种情况。

要计算字符长度，我们在 298-计算字符长度中讨论过解法，思路有两种：

第一种，遍历字符，将字符转换成元组，元组 length 就是要求的长度，代码如下：

type StringToUnion<S extends string> = S extends `${string}${infer R}`
  ? [1, ...StringToUnion<R>]
  : [];

// Case1 = 20
type Case1 = StringToUnion<'12345678901234567890'>['length'];

第二种，也是遍历字符，通过增加一个辅助的计数元组，每次遍历一个字符，就往辅助元组里塞一个值，最终，遍历结束，辅助元组的长度就是题解。代码如下：

type LengthOfString<
  S extends string,
  Arr extends any[] = [],
> = S extends `${string}${infer R}`
  ? LengthOfString<R, [...Arr, 1]>
  : Arr['length'];

// Case2 = 20
type Case2 = LengthOfString<'12345678901234567890'>;

这两种解法看着没什么区别，但是当字符长度达到 49 时，解法一，就会出现 Type instantiation is excessively deep and possibly infinite.ts(2589) 这个问题，而解法二，会在字符长度达到 1000 时，才会出现这个问题。

此时，我不知道读者第一次看到这两种解法对不同长度字符的处理有区别时，是什么感受，我内心的感受可以用这个表情包感受下：

。

黑人问号脸.jpg

同样是递归，这有啥区别？为什么第一种解法只能递归 50 次，而解法二，能够到 1000 呢？

# 尾调用、尾递归

以下来自维基百科 (opens new window)：

在计算机学里，尾调用是指一个函数里的最后一个动作是返回一个函数的调用结果的情形，即最后一步新调用的返回值直接被当前函数的返回结果。此时，该尾部调用位置被称为尾位置。尾调用中有一种重要而特殊的情形叫做尾递归。经过适当处理，尾递归形式的函数的运行效率可以被极大地优化。尾调用原则上都可以通过简化函数调用栈的结构而获得性能优化（称为“尾调用消除”），但是优化尾调用是否方便可行取决于运行环境对此类优化的支持程度如何。

关于 js 中的尾调用优化，可以参考阮老师的文章 (opens new window)。文章写的简单通透，我就不在这里做重复工作了。

# ts 中的尾递归优化

通过搜索 ts 的 checker.ts 代码，具体可以查看源码 (opens new window) 中搜索: Type_instantiation_is_excessively_deep_and_possibly_infinite。

可以浅显的看到：

if (tailCount === 1000) {
  error(
    currentNode,
    Diagnostics.Type_instantiation_is_excessively_deep_and_possibly_infinite,
  );
  result = errorType;
  break;
}

如果尾递归超过了 1000，会报这个错误。

而单纯的递归：

function instantiateTypeWithAlias(
  type: Type,
  mapper: TypeMapper,
  aliasSymbol: Symbol | undefined,
  aliasTypeArguments: readonly Type[] | undefined,
): Type {
  if (!couldContainTypeVariables(type)) {
    return type;
  }
  if (instantiationDepth === 100 || instantiationCount >= 5000000) {
    // We have reached 100 recursive type instantiations, or 5M type instantiations caused by the same statement
    // or expression. There is a very high likelyhood we're dealing with a combination of infinite generic types
    // that perpetually generate new type identities, so we stop the recursion here by yielding the error type.
    tracing?.instant(tracing.Phase.CheckTypes, 'instantiateType_DepthLimit', {
      typeId: type.id,
      instantiationDepth,
      instantiationCount,
    });
    error(
      currentNode,
      Diagnostics.Type_instantiation_is_excessively_deep_and_possibly_infinite,
    );
    return errorType;
  }
  totalInstantiationCount++;
  instantiationCount++;
  instantiationDepth++;
  const result = instantiateTypeWorker(
    type,
    mapper,
    aliasSymbol,
    aliasTypeArguments,
  );
  instantiationDepth--;
  return result;
}

在深度超过了 100 或者内存占用超过了 5M，也会报这个错误。

但是实际用下来，应该是超过 50 就会报错，这块的逻辑有懂的可以联系我 (也可拉你进群一起提讨论提 PR)，非常乐意讨论交流。

# 结论

对于上述计算字符长度的解法一：

type StringToUnion<S extends string> = S extends `${string}${infer R}`
  ? [1, ...StringToUnion<R>]
  : [];

// Case1 = 20
type Case1 = StringToUnion<'12345678901234567890'>['length'];

它的返回值并不是一个函数执行的返回值，所以并没有触发尾调用，此时深度只能达到 50 (但是看代码是 100，这块我也不清楚了)

对于解法二：

type LengthOfString<
  S extends string,
  Arr extends any[] = [],
> = S extends `${string}${infer R}`
  ? LengthOfString<R, [...Arr, 1]>
  : Arr['length'];

// Case2 = 20
type Case2 = LengthOfString<'12345678901234567890'>;

返回值，就是自身，触发了尾递归，此时深度可以达到 1000。

好了，这就是关于 ts 中递归深度的讨论，

← 基操-判断两个类型相等基操-箭头函数重载 →