尾递归的后续探究

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 条评论
登录 后参与评论

相关文章

来自专栏Python中文社区

关于生成器的那些事儿

关于生成器的那些事儿 作者:李者璈 写在前面的话 ❈ 本来想这周继续写写 Flask 那点破事儿的,但是想了想决定换换口味,来聊聊很不容易理解但是很重要的 Py...

1819
来自专栏web前端教室

=>,Es6箭头符号的前世今生

看代码能看错行,一看书就头疼且双眼流泪,没办法啊,都是娘胎里带出来的毛病,能看点是点吧。es6这种东西,虽然有一些语法糖,但毕竟也是新东西啊,得学。不学就落后,...

19310
来自专栏magicsoar

Effective Modern C++翻译(1):序言

/*********************************************************** 关于书: 书是我从网上找到的effec...

1799
来自专栏互联网杂技

12条专业的JavaScript规则

习JavaScript是困难的。它发展的如此之快,以至于在任何一个特定的时刻,你都不清楚自己是否“做错了”。有些时候,感觉像是坏的部分超过了好的部分。然而,讨论...

3399
来自专栏大闲人柴毛毛

使用Eclipse插件提高Java编码质量

代码质量概述 ? 怎样辨别一个项目代码写得好还是坏?优秀的代码和腐化的代码区别在哪里?怎么让自己写的代码既漂亮又有生命力?接下来将对代码质量的问题进行...

2757
来自专栏web前端教室

[先行者计划]:《Vuex相关概念的讲解和介绍》-- 课堂笔记节选

vuex是什么东西? 官网对Vuex的定义,"Vuex 是一个专为 Vue.js 应用程序开发的状态管理模式。" 恩,从这句话可以看出,它应该是一种编写js的思...

1648
来自专栏平凡文摘

怎样编写高质量的Java代码

1183
来自专栏企鹅号快讯

Python 相较于Java 而言,有什么优势?

最近在后台,有很多的同学私聊我说,Python和Java.,哪个具有前景呢?今天我们就来简单的讲一下这两者的区别: 我认为C, Java跟Python都是非常成...

2036
来自专栏精讲JAVA

怎样编写高质量的Java代码

代码质量概述 怎样辨别一个项目代码写得好还是坏?优秀的代码和腐化的代码区别在哪里?怎么让自己写的代码既漂亮又有生命力?接下来将对代码质量的问题进行一些粗略的介绍...

41510
来自专栏怀英的自我修炼

Java漫谈7

这次我们聊聊上次没有聊到的switch语句。 首先设想这么一种去吃饭的场景,我进到美食城,看着各种各样的餐馆,不知道吃什么好的时候,选择就变得尤其重要。我可以按...

3378

扫码关注云+社区