如何让 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 不优化 tail-called 递归函数。请参阅 microsoft/TypeScript#32743 以获得权威答案。

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

如果您建议 TypeScript 实施 尾调用优化 作为性能改进，那不适合 TypeScript's design goals。一般来说，如果您为目标运行时间环境编写了语法正确 JavaScript 的代码，编译器将发出该代码 as-is。 TypeScript 不应该优化你的 JavaScript，只是发出它。所以它不可能自己做到这一点。

另一方面，您可能在谈论 适当的尾调用消除，如 ECMAScript 2015 (ES2015/ES6) 规范中所介绍的那样。此功能旨在让 JavaScript 运行时间引擎能够检测到尾部调用，并且在这种情况下不会添加到调用堆栈。

此功能从未被广泛采用； currently 只有 Safari-based 浏览器似乎一直这样做。

当运行time 引擎设计人员考虑实现此功能时，他们运行研究了可能的性能下降、开发人员混淆等问题。参见 this V8 blog post for example. Most runtime engines seem to have opted for a "wait-and-see" approach for some more desirable version of this, such as a syntax to explicitly opt in to such elimination. And the only notable proposal for such syntax 多年来一直“不活跃” .所以看起来“wait-and-see”的“等待”部分可能永远持续下去。

虽然 TypeScript 有可能 downlevel 适当地消除尾调用优化之类的东西，但它可能运行解决同样的问题，他们拒绝这样做。

无论好坏，自动尾调用消除似乎是一个 de-facto 死的功能，TypeScript 不会为我们复活它。

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

How can I get TypeScript to perform Tail Recursion Optimization?

javascript

typescript

optimization

compiler-optimization

tail-recursion