尾部调用优化（TCO）

通常来说，当从一个函数内部发起对另一个函数的调用时，就会分配一个 栈帧 来分离地管理这另一个函数调用的变量/状态。这种分配不仅花费一些处理时间，还会消耗一些额外的内存。

一个调用栈链从一个函数到另一个再到另一个，通常至多拥有10-15跳。在这些场景下，内存使用不太可能是某种实际问题。

然而，当你考虑递归编程（一个函数频繁地调用自己） —— 或者使用两个或更多的函数相互调用而构成相互递归 —— 调用栈就可能轻易地到达上百，上千，或更多层的深度。如果内存的使用无限制地增长下去，你可能看到了它将导致的问题。

JavaScript引擎不得不设置一个随意的限度来防止这样的编程技术耗尽浏览器或设备的内存。这就是为什么我们会在到达这个限度时得到令人沮丧的“RangeError: Maximum call stack size exceeded”。

警告： 调用栈深度的限制是不由语言规范控制的。它是依赖于具体实现的，而且将会根据浏览器和设备不同而不同。你绝不应该带着可精确观察到的限度的强烈臆想进行编码，因为它们还很可能在每个版本中变化。

一种称为 尾部调用 的特定函数调用模式，可以以一种避免额外的栈帧分配的方法进行优化。如果额外的分配可以被避免，那么就没有理由随意地限制调用栈的深度，这样引擎就可以让它们没有边界地运行下去。

一个尾部调用是一个带有函数调用的return语句，除了返回它的值，函数调用之后没有任何事情需要发生。

这种优化只能在strict模式下进行。又一个你总是应该用strict编写所有代码的理由！

这个函数调用 不是 在尾部：

  1. "use strict";
  3. function foo(x) {
  4.     return x * 2;
  5. }
  7. function bar(x) {
  8.     // 不是一个尾部调用
  9.     return 1 + foo( x );
  10. }
  12. bar( 10 );                // 21

在foo(x)调用完成后必须进行1 + ..，所以那个bar(..)调用的状态需要被保留。

但是下面的代码段中展示的foo(..)和bar(..)都是位于尾部，因为它们都是在自身代码路径上（除了return以外）发生的最后一件事：

  1. "use strict";
  3. function foo(x) {
  4.     return x * 2;
  5. }
  7. function bar(x) {
  8.     x = x + 1;
  9.     if (x > 10) {
  10.         return foo( x );
  11.     }
  12.     else {
  13.         return bar( x + 1 );
  14.     }
  15. }
  17. bar( 5 );                // 24
  18. bar( 15 );                // 32

在这个程序中，bar(..)明显是递归，但foo(..)只是一个普通的函数调用。这两个函数调用都位于 恰当的尾部位置。x + 1在bar(..)调用之前被求值，而且不论这个调用何时完成，所有将要放生的只有return。

这些形式的恰当尾部调用（Proper Tail Calls —— PTC）是可以被优化的 —— 称为尾部调用优化（TCO）—— 于是额外的栈帧分配是不必要的。与为下一个函数调用创建新的栈帧不同，引擎会重用既存的栈帧。这能够工作是因为一个函数不需要保留任何当前状态 —— 在PTC之后的状态下不会发生任何事情。

TCO意味着调用栈可以有多深实际上是没有限度的。这种技巧稍稍改进了一般程序中的普通函数调用，但更重要的是它打开了一扇大门：可以使用递归表达程序，即使它的调用栈深度有成千上万层。

我们不再局限于单纯地在理论上考虑用递归解决问题了，而是可以在真实的JavaScript程序中使用它！

作为ES6，所有的PTC都应该是可以以这种方式优化的，不论递归与否。

重写尾部调用

然而，障碍是只有PTC是可以被优化的；非PTC理所当然地依然可以工作，但是将造成往常那样的栈帧分配。如果你希望优化机制启动，就必须小心地使用PTC构造你的函数。

如果你有一个没有用PTC编写的函数，你可能会发现你需要手动地重新安排你的代码，使它成为合法的TCO。

考虑如下代码：

  1. "use strict";
  3. function foo(x) {
  4.     if (x <= 1) return 1;
  5.     return (x / 2) + foo( x - 1 );
  6. }
  8. foo( 123456 );            // RangeError

对foo(x-1)的调用不是一个PTC，因为在return之前它的结果必须被加上(x / 2)。

但是，要使这段代码在一个ES6引擎中是合法的TCO，我们可以像下面这样重写它：

  1. "use strict";
  3. var foo = (function(){
  4.     function _foo(acc,x) {
  5.         if (x <= 1) return acc;
  6.         return _foo( (x / 2) + acc, x - 1 );
  7.     }
  9.     return function(x) {
  10.         return _foo( 1, x );
  11.     };
  12. })();
  14. foo( 123456 );            // 3810376848.5

如果你在一个实现了TCO的ES6引擎中运行前面这个代码段，你将会如展示的那样得到答案3810376848.5。然而，它仍然会在非TCO引擎中因为RangeError而失败。

非TCO优化

有另一种技术可以重写代码，让调用栈不随每次调用增长。

一个这样的技术称为 蹦床，它相当于让每一部分结果表示为一个函数，这个函数要么返回另一个部分结果函数，要么返回最终结果。然后你就可以简单地循环直到你不再收到一个函数，这时你就得到了结果。考虑如下代码：

  1. "use strict";
  3. function trampoline( res ) {
  4.     while (typeof res == "function") {
  5.         res = res();
  6.     }
  7.     return res;
  8. }
  10. var foo = (function(){
  11.     function _foo(acc,x) {
  12.         if (x <= 1) return acc;
  13.         return function partial(){
  14.             return _foo( (x / 2) + acc, x - 1 );
  15.         };
  16.     }
  18.     return function(x) {
  19.         return trampoline( _foo( 1, x ) );
  20.     };
  21. })();
  23. foo( 123456 );            // 3810376848.5

这种返工需要一些最低限度的改变来将递归抽出到trampoline(..)中的循环中：

  1. 首先，我们将return _foo ..这一行包装进函数表达式return partial() {..。
  2. 然后我们将_foo(1,x)包装进trampoline(..)调用。

这种技术之所以不受调用栈限制的影响，是因为每个内部的partial(..)函数都只是返回到trampoline(..)的while循环中，这个循环运行它然后再一次循环迭代。换言之，partial(..)并不递归地调用它自己，它只是返回另一个函数。栈的深度维持不变，所以它需要运行多久就可以运行多久。

蹦床表达的是，内部的partial()函数使用在变量x和acc上的闭包来保持迭代与迭代之间的状态。它的优势是循环的逻辑可以被抽出到一个可重用的trampoline(..)工具函数中，许多库都提供这个工具的各种版本。你可以使用不同的蹦床算法在你的程序中重用trampoline(..)多次。

当然，如果你真的想要深度优化（于是可复用性不予考虑），你可以摒弃闭包状态，并将对acc的状态追踪，与一个循环一起内联到一个函数的作用域内。这种技术通常称为 递归展开：

  1. "use strict";
  3. function foo(x) {
  4.     var acc = 1;
  5.     while (x > 1) {
  6.         acc = (x / 2) + acc;
  7.         x = x - 1;
  8.     }
  9.     return acc;
  10. }
  12. foo( 123456 );            // 3810376848.5

算法的这种表达形式很容易阅读，而且很可能是在我们探索过的各种形式中性能最好的（严格地说）一个。很明显它看起来是一个胜利者，而且你可能会想知道为什么你曾尝试其他的方式。

这些是为什么你可能不想总是手动地展开递归的原因：

  • 与为了复用而将弹簧（循环）逻辑抽出去相比，我们内联了它。这在仅有一个这样的例子需要考虑时工作的很好，但只要你在程序中有五六个或更多这样的东西时，你将很可能想要一些可复用性来将让事情更简短、更易管理一些。

  • 这里的例子为了展示不同的形式而被故意地搞得很简单。在现实中，递归算法有着更多的复杂性，比如相互递归（有多于一个的函数调用它自己）。

    你在这条路上走得越远，展开 优化就变得越复杂和越依靠手动。你很快就会失去所有可读性的认知价值。递归，甚至是PTC形式的递归的主要优点是，它保留了算法的可读性，并将性能优化的任务交给引擎。

如果你使用PTC编写你的算法，ES6引擎将会实施TCO来使你的代码运行在一个定长深度的栈中（通过重用栈帧）。你将在得到递归的可读性的同时，也得到性能上的大部分好处与无限的运行长度。

元？

TCO与元编程有什么关系？

正如我们在早先的“特性测试”一节中讲过的，你可以在运行时判定一个引擎支持什么特性。这也包括TCO，虽然判定的过程相当粗暴。考虑如下代码：

  1. "use strict";
  3. try {
  4.     (function foo(x){
  5.         if (x < 5E5) return foo( x + 1 );
  6.     })( 1 );
  8.     TCO_ENABLED = true;
  9. }
  10. catch (err) {
  11.     TCO_ENABLED = false;
  12. }

在一个非TCO引擎中，递归循环最终将会失败，抛出一个被try..catch捕获的异常。否则循环将由TCO轻易地完成。

讨厌，对吧？

但是围绕着TCO特性进行的元编程（或者，没有它）如何给我们的代码带来好处？简单的答案是你可以使用这样的特性测试来决定加载一个你的应用程序的使用递归的版本，还是一个被转换/转译为不需要递归的版本。

自我调整的代码

但这里有另外一种看待这个问题的方式：

  1. "use strict";
  3. function foo(x) {
  4.     function _foo() {
  5.         if (x > 1) {
  6.             acc = acc + (x / 2);
  7.             x = x - 1;
  8.             return _foo();
  9.         }
  10.     }
  12.     var acc = 1;
  14.     while (x > 1) {
  15.         try {
  16.             _foo();
  17.         }
  18.         catch (err) { }
  19.     }
  21.     return acc;
  22. }
  24. foo( 123456 );            // 3810376848.5

这个算法试图尽可能多地使用递归来工作，但是通过作用域中的变量x和acc来跟踪这个进程。如果整个问题可以通过递归没有错误地解决，很好。如果引擎在某一点终止了递归，我们简单地使用try..catch捕捉它，然后从我们离开的地方再试一次。

我认为这是一种形式的元编程，因为你在运行时期间探测着引擎是否能（递归地）完成任务的能力，并绕过了任何可能制约你的（非TCO的）引擎的限制。

一眼（或者是两眼！）看上去，我打赌这段代码要比以前的版本难看许多。它运行起来还相当地慢一些（在一个非TCO环境中长时间运行的情况下）。

它主要的优势是，除了在非TCO引擎中也能完成任意栈大小的任务外，这种对递归栈限制的“解法”要比前面展示的蹦床和手动展开技术灵活得多。

实质上，这种情况下的_foo()实际上是任意递归任务，甚至是相互递归的某种替身。剩下的内容是应当对任何算法都可以工作的模板代码。

唯一的“技巧”是为了能够在达到递归限制的事件发生时继续运行，递归的状态必须保存在递归函数外部的作用域变量中。我们是通过将x和acc留在_foo()函数外面这样做的，而不是像早先那样将它们作为参数值传递给_foo()。

几乎所有的递归算法都可以采用这种方法工作。这意味着它是在你的程序中，进行最小的重写就能利用TCO递归的最广泛的可行方法。

这种方式仍然使用一个PTC，意味着这段代码将会 渐进增强：从在一个老版浏览器中使用许多次循环（递归批处理）来运行，到在一个ES6+环境中完全利用TCO递归。我觉得这相当酷！