尾递归的后续探究

0 前言

去年大致也是这个事件，曾经探索过尾调用（PTC）相关的内容，并总结了一片文章——朋友你听说过尾递归吗。同时在文章的最后也留下了一个坑：

尾递归写法的函数在Chrome浏览器的控制台下依旧出现了调用栈溢出的异常。

机缘巧合下又回想起了这个问题，今天就决定把这个坑给填上。

1 ECMAScript兼容性

先带大家看一眼ES6在各大平台上的兼容性：

大家可以发现其实每次进入ES6兼容表的时候，功能行的第一行就是我们的尾递归调用（proper tail calls）,而它的兼容性也可以看出是满片飘红啊。

这也就是上文提到调用栈溢出的直接原因，各大浏览器（除了safari）根本就没部署尾调用优化，直接在浏览器上的控制台上调试尾递归的代码当然还是会出现栈溢出的问题。

施工中... 待补上safari的运行例子，windows版的safari（5.1.7）已经停止更新。

2 一个真正尾调用优化的例子

// PTC.js
'use strict';

// 计算1-N的累加值（尾递归）
function f(n, sum = 1) {
    if (n <= 1) {
        return sum;
    }
    return f(n - 1, sum + n);
}
const result = f(100000);
console.log(result);

V8引擎实际上已经实现了尾调用优化，但是默认是关闭该功能的。

执行 node --v8-options 可以找到一个启用尾调用优化的参数--harmony_tailcalls

--harmony_tailcalls (enable "harmony tail calls" (in progress)) 
    type: bool  default: false

所以我们执行node --harmony_tailcalls PTC.js就可以看到尾调用优化下的递归方法正确的计算出了我们想要的值。

那么为什么V8引擎都已经实现了尾调用优化，但是默认不开启呢？

3 尾调用优化默认关闭

V8 blog里有这么一篇文章《ES6, ES7 and beyond》给了我们对应的解释。

3.1 隐式优化问题

首先，由于引擎消除尾递归是隐式的，函数是否符合尾调用而被消除了尾递归很难被程序员自己辨别。

也就是说，我们写出来的代码希望引擎自动帮我们进行优化的时候，我们不一定清楚“编码出来的尾递归”是不是写对了？是否能被引擎自动识别出来并优化呢？

为了写出正确的尾递归方法，你需要首先了解是不是正确的尾调用形式。同时你可能还需要尝试写不同的尾递归和普通递归的写法，调整递归参数让能超过调用栈，并不断的进行调试。而且你也不能保证调试出来的结果是不是因为运气好而表现出了正常的结果。这也就是隐式优化所带来的一大问题。

3.2 调用栈丢失问题

其次，尾调用优化要求除掉尾调用执行时的调用堆栈，这将导致执行流中的堆栈信息丢失。

这也就导致依赖调用堆栈信息的调试和错误收集过程受到了影响。

相关影响内容在作者之前的文章中也有提及——PTC存在的问题

这也就是上文提到调用栈溢出的根本原因，尾调用优化已经被实现但是没有在特性中默认支持的理由目前正在TC39标准委员会中讨论，感兴趣的同学也可以看看。

4 STC

尾调用优化存在的问题其实是在于其优化过程是不受开发者控制和了解的，所以来自 Mozilla 和微软的委员提出从语法上指定尾部调行为（Syntactic Tail Call）。语义上的尾调用是针对上述PTC的问题而提出的建议。

STC采用类似于 return continue 的语法来明确标识出要进行尾调用优化，而在非尾调用的场景下使用该语法会抛出语法错误异常。STC有语法、函数、表达式等多种形式。

同样的STC对比PTC也有两个缺点：

• 渐进增强： 一些值的计算需要在不断的递归中得到逼近的值，PTC的写法可以帮助得到一个爆栈前的值；
• 维护难度： 新的语法意味着需要维护两套后端；

5 总结

Chrome下使用尾递归写法的方法依旧出现调用栈溢出的原因在于：

• 直接原因： 各大浏览器（除了safari）根本就没部署尾调用优化
• 根本原因： 尾调用优化依旧有隐式优化和调用栈丢失的问题

参考资料

朋友你听说过尾递归吗 JS中尾递归STC与PTC（hax演讲视频） ES6, ES7 and beyond V8 团队眼中的 ES6、ES7及未来 Tail call optimization in ECMAScript 6

一定要把Z键修好再写文章...