专栏首页IMWeb前端团队尾递归的后续探究

尾递归的后续探究

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键修好再写文章...

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 非极大值抑制(Non-Maximum Suppression)

    博客:noahsnail.com  |  CSDN  |  简书 |   云+社区

    Tyan
  • 算法:大O符号解释

    O(n),O(1),O(log n)等大O符号被用来表示算法的效率。在这篇文章中,你会找到每个大O符号的例子和解释。

    大数据弄潮儿
  • 全面、简单理解朴素贝叶斯(Naive Bayes)

    朴素贝叶斯(Naive Bayes)是经典的机器学习算法之一,也是为数不多的基于概率论的分类算法。本文可能是目前网络上最全面也最简单易懂的有关朴素贝叶斯的文章。

    挖掘大数据
  • 深度学习与强化学习

    随着 DeepMind 公司的崛起,深度学习和强化学习已经成为了人工智能领域的热门研究方向。除了众所周知的 AlphaGo 之外,DeepMind 之前已经使用...

    张戎
  • 腾讯赵建春:AI浪潮下的高效运维思考及实践

    腾讯 SNG 助理总经理、GOPS 金牌讲师赵建春老师受邀出席大会,并带来精彩演讲《AI 浪潮下的高效运维思考与实践》。

    织云平台团队
  • FPGA : 用“芯”做图

    图像的压缩,从本质上是通过提高计算算力来降低存储和带宽。同时更加复杂的算法也带来计算算力的大量消耗和处理延时的增加。

    腾讯架构师
  • 15个顶级Java多线程面试题及答案

    在任何Java面试当中多线程和并发方面的问题都是必不可少的一部分。如果你想获得任何股票投资银行的前台资讯职位,那么你应该准备很多关于多线程的问题。在投资银行业务...

    Java后端工程师
  • 让大象起舞:HTTPS 计算性能优化

    HTTPS 很安全,与此同时却又要消耗非常多的CPU资源,STGW 针对 nginx 和 openssl 进行了大量优化,用以提升 HTTPS 的计算性能和访问...

    腾讯技术工程官方号
  • 京东首届”JDD-2017京东金融全球数据探索者大赛”中国区算法组落下帷幕

    2月17日,在经历了48小时的极限挑战之后,首届”JDD-2017京东金融全球数据探索者大赛”算法组全球总决赛和商业组中国区决赛落下帷幕。算法组四大赛题冠军分别...

    人工智能的秘密
  • 神经网络模型求解思路

    神经网络模型,mini_batch 批梯度下降(SGD)求解权重参数的原理见:深度学习|神经网络模型简介和梯度下降求解,这篇文章中用一个小球下坡,解释了各个节点...

    人工智能的秘密

扫码关注云+社区

领取腾讯云代金券