尾递归的后续探究

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

相关文章

来自专栏转载gongluck的CSDN博客

cocos2dx 打灰机

#include "GamePlane.h" #include "PlaneSprite.h" #include "BulletNode.h" #include...

7256
来自专栏张善友的专栏

Mix 10 上的asp.net mvc 2的相关Session

Beyond File | New Company: From Cheesy Sample to Social Platform Scott Hansel...

2787
来自专栏张善友的专栏

Silverlight + Model-View-ViewModel (MVVM)

     早在2005年,John Gossman写了一篇关于Model-View-ViewModel模式的博文,这种模式被他所在的微软的项目组用来创建Expr...

3308
来自专栏pangguoming

Spring Boot集成JasperReports生成PDF文档

由于工作需要,要实现后端根据模板动态填充数据生成PDF文档,通过技术选型,使用Ireport5.6来设计模板,结合JasperReports5.6工具库来调用渲...

1.4K7
来自专栏java 成神之路

使用 NIO 实现 echo 服务器

5617
来自专栏张善友的专栏

LINQ via C# 系列文章

LINQ via C# Recently I am giving a series of talk on LINQ. the name “LINQ via C...

3015
来自专栏我和未来有约会

Kit 3D 更新

Kit3D is a 3D graphics engine written for Microsoft Silverlight. Kit3D was inita...

2936
来自专栏Golang语言社区

【Golang语言社区】GO1.9 map并发安全测试

var m sync.Map //全局 func maintest() { // 第一个 YongHuomap := make(map[st...

5478
来自专栏张善友的专栏

Miguel de Icaza 细说 Mix 07大会上的Silverlight和DLR

Mono之父Miguel de Icaza 详细报道微软Mix 07大会上的Silverlight和DLR ,上面还谈到了Mono and Silverligh...

3007
来自专栏我和未来有约会

Silverlight第三方控件专题

这里我收集整理了目前网上silverlight第三方控件的专题,若果有所遗漏请告知我一下。 名称 简介 截图 telerik 商 RadC...

4405

扫码关注云+社区