如何让 TypeScript 执行尾递归优化？

Question

const isPositive = (n: number) => n > 0;

function fitsIn(dividend: number,
                divisor: number,
                count: number,
                accum: number): number {
  if (accum + divisor > dividend) {
    return count;
  }
  return fitsIn(dividend, divisor, count + 1, accum + divisor);
}

function divide(dividend: number, divisor: number): number {
  let timesFits = fitsIn(Math.abs(dividend), Math.abs(divisor), 0, 0);
  return isPositive(dividend) === isPositive(divisor) ? timesFits : -timesFits;
}

console.log(divide(10, 3));
// 3

console.log(divide(-2147483648, -1));
// RangeError: Maximum call stack size exceeded

console.log(divide(10000, 1));
// RangeError: Maximum call stack size exceeded

我尝试在严格模式下使用 TypeScript 4.6.2 运行此代码，它导致堆栈溢出。递归调用位于函数末尾，累加在递归函数调用内部完成。这段代码不应该针对尾递归进行优化吗？应该改变什么才能实现尾递归优化？

Answer 1

TypeScript 不会优化尾部调用的递归函数。请参阅 microsoft/TypeScript#32743 获取权威答案。

通常，JavaScript 中的术语“尾调用优化”表示将尾递归函数重写为迭代版本。这与“尾部调用消除”有所不同，“尾部调用消除”通常意味着保留递归但重写当前堆栈帧，而不是将新堆栈帧推入堆栈。如果您只关心堆栈增长，那么从外部来看，两者的行为类似，但尾调用优化通常发生在高于尾调用消除的抽象级别。

---

如果您建议 TypeScript 实现 尾调用优化 作为性能改进，那么这不符合 TypeScript 的设计目标。一般来说，如果您为目标运行时环境编写了一些语法正确的 JavaScript 代码，编译器将按原样发出该代码。 TypeScript 不应该优化你的 JavaScript，只是发出它。所以它自己不可能做到这一点。

---

另一方面，您可能会谈论“正确的尾部调用消除”，如 ECMAScript 2015 (ES2015/ES6) 规范中所介绍的那样。此功能的目的是让 JavaScript 运行时引擎能够检测尾部调用，并且在这种情况下不会添加到调用堆栈中。 此功能从未被广泛采用；

目前

只有基于 Safari 的浏览器似乎始终这样做。 当运行时引擎设计者考虑实现这一点时，他们遇到了可能的性能下降、开发人员困惑等问题。例如，请参阅

这篇 V8 博客文章

。大多数运行时引擎似乎都选择了“观望”方法来实现一些更理想的版本，例如显式选择这种消除的语法。而且这种语法的唯一“值得注意的提案”多年来一直“不活跃”。所以看来“观望”中的“等待”部分可能会永远持续下去。 虽然 TypeScript 可以下级将尾调用消除适当地转化为尾调用优化之类的东西，但它很可能会遇到同样的问题，而且他们拒绝这样做。

无论好坏，看起来自动尾部调用消除实际上是一个已失效的功能，TypeScript 不会为我们复活它。

---

这个

Answer 2

课程可能就是您需要的东西。

const rem = 
(n: number, r: number)
: fp.TailCall<number> =>
    
    (n < r) ? fp.TailCall.done(n) 
    : fp.TailCall.call(() => rem(n-r, r)) ;

console.log(rem(10000001,2).invoke()); // wait, out: 1

这是

这个java博客

的TS模拟。