JS 中的递归优化——它在哪里？PTC、TCO 和 FUD

ES6 已经过时了。它已经在所有现代浏览器上全面支持了。这里没什么可看的。
我们之前用来查看进度的 kangax 的 ES6 compat-table 现在应该已经全部绿了，对吧？

嗯，事实并非如此。

正确的尾部调用部分（尾部调用优化）是红色的。

为什么？这是 JS 无法实现的功能吗？
嗯，不是。只有一个浏览器实现了这个功能：Safari。

那么这是可能的，而且它已经在 Safari 中面向大量用户推出。为什么 Chrome 和 Firefox 会落后呢？

答案很复杂。而且，从我浏览过 V8、Firefox JS 引擎、GitHub 问题、TC39 委员会讨论等众多 bug 跟踪器的评论来看，这些评论也非常政治化，而且带有主观性。

我将尝试在这里介绍一些有关该主题的背景知识，希望可以让您更多地了解为什么这件事如此困难。

总拥有成本？

PTC - 正确尾调用
TCO - 尾代码优化
这两个术语并不相同。理解它们之间的区别对于接下来的讨论至关重要。

未来的假设

我不想把这篇文章变成递归和调用栈的入门教程。
我假设你已经了解这部分内容了。如果你不了解，freecodecamp上有一篇很棒的文章。

正确的尾调用

在开始之前，我想说，ES6 应该实现的是合理的尾调用，而不是尾部代码优化（我们稍后会讨论）。
它包含在ES6 标准文档中，如果你看不懂它的正式定义（别担心，我也看不懂），你可以直接看介绍：

Goals for ECMAScript 2015 include providing better support for [...].
Some of its major enhancements include modules, class declarations, [..]
and proper tail calls.

正确的尾调用是一种技术，程序不会为符合尾调用定义的递归创建额外的堆栈帧。
这，而且这才是正确的尾调用的价值主张。

因此，我们不会将递归的所有堆栈都保存在内存中，而是只保存一级堆栈，从而优化递归堆栈。

但怎么可能呢？尾递归函数基本上会不断传递递归所需的所有必要数据，因此您不必依赖堆栈。

这里的经典例子是斐波那契函数。

在经典（头部）递归中考虑这一点：

function factorial(n) {
  if (n === 0) {
    return 1
  }
  return n * factorial(n - 1)
}

它必须在每一步都依赖堆栈，因为每一步都必须“处理”到n * factorial(n - 1)。

现在考虑这个尾递归版本：

function factorial(n, acc = 1) {
  if (n === 0) {
    return acc
  }
  return factorial(n - 1, n * acc)
}

在这个版本中，我们有一个累加器作为参数。它跟踪到目前为止的总数。因此，这里的堆栈没有任何用处，所有数据在整个递归调用过程中都可用。

太棒了！递归编程有时比迭代更容易掌握，而且没有调用堆栈的问题。它们基本上是等价的！

只是，事实并非如此。在 PTC 的案例中并非如此。PTC
的问题在 Ecmascript 中最近关于 TCO 的提案中得到了精彩的描述。

基本上，它们就是这样的：

• 性能问题。这仅优化了调用堆栈，而不是调用本身。
• 调试。调用堆栈将会被不自然地篡改，这可能会使调试变得更加困难。

哎呀。难怪大家对这方面如此热衷。
有人说调试问题会毁了交易，性能问题会毁了性能分析。另一些人则认为这只是 FUD（恐惧、怀疑和未知），因为 Safari 已经实现了 PTC，而且地狱还没关闭。

您可以在这里找到成年人为自己的信仰而热情奋斗：
https://github.com/tc39/proposal-ptc-syntax/issues/23
https://bugs.chromium.org/p/v8/issues/detail?id=4698

尾调用优化

尾调用优化来拯救你了！
其实也没那么简单，但我想说得更夸张一些。

尾部代码优化的不同之处在于它不是简单地消除额外的堆栈调用，而是将递归函数完全重新编译为迭代函数。

在幕后，尾部代码优化采用递归函数并生成迭代函数，goto在内部使用，然后运行它。

它不限制堆栈调用，因为一旦函数实际上在后台不递归，就不会有堆栈调用。

这完美地解决了性能问题。Lua
其实很久以前就实现了这个功能，而且运行完美。递归函数的性能与其等效的迭代函数相同。

好吧，那么为什么不直接实施 TCO 呢？

嗯……关于这一点也有很多争论。
有些人想要“隐式”TCO——也就是说，当它识别出一个适合尾部优化的函数时——就直接执行。

还有一些人想要“明确的” TCO——只有当这是开发人员的意图时才这样做。

这就是当前关于句法尾调用的提案的全部内容。

它为尾调用优化引入了新的语法和新的关键字，即continue关键字。

而且，这里似乎也再次存在很多争议。

• 我们是否必须恳求第三方库所有者重写他们的代码？
• 所需的新语法基本上会在任何人使用之前扼杀该功能。
• 等等'等等'。

好了，这就是 JS 尾调用优化的现状。
当然，我没有深入探讨细节，但我觉得这应该能让你对这个问题的复杂性和难以解决的原因有一个基本的了解。
一如既往，感谢所有致力于此主题和 Ecmascript 提案的朋友们。你们的工作和充满激情的讨论最终让我们所有人都受益匪浅。