尾递归的后续探究

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

相关文章

来自专栏chafezhou

小说python的类型提示(type hints)

大家都知道python是一门动态类型的语言,但作者Guido van Rossum在2014年创建PEP-484添加了类型提示,在python3.5的版本中正式...

721
来自专栏Python研发

一起来学Go --- (go的简介以及环境的安装)

相信大家,看到这篇文章的时候,已经自己在百度百科了解了go的发展史已经特性,再次我依然。。。。得哔哔叨一会。   ^.^

1011
来自专栏Java技术

如何避免自己写的代码成为别人眼中的一坨屎!

摘要: Any fool can write code that a computer can understand. Good programmers wri...

531
来自专栏GopherCoder

『No25: 编写可读代码的艺术(2)』

根据:先处理正向逻辑,处理简单的,处理可疑或者有趣的准则,改善如下(仅仅只是调换顺序)

622
来自专栏Java工程师日常干货

使用Google Guava快乐编程以面向对象思想处理字符串:Joiner/Splitter/CharMatcher对基本类型进行支持对JDK集合的有效补充函数式编程:Functions断言:Pred

目前Google Guava在实际应用中非常广泛,本篇博客将以博主对Guava使用的认识以及在项目中的经验来给大家分享!正如标题所言,学习使用Google Gu...

723
来自专栏平凡文摘

Java 8 最佳技巧

1433
来自专栏Linyb极客之路

如何避免自己写的代码成为别人眼中的一坨屎!

普通的工程师堆砌代码,优秀的工程师优雅代码,卓越的工程师简化代码。如何写出优雅整洁易懂的代码是一门学问,也是软件工程实践里重要的一环。笔者推荐三本经典的书籍《代...

1237
来自专栏海天一树

小朋友学C++(2):面向过程与面向对象

先用C++编写一个加法程序 #include <iostream> using namespace std; int add(int a, int b) { ...

3239
来自专栏哲学驱动设计

模式应用:自定义匹配

    本篇博客记录了我在工作过程中的一个设计单元。 需求 GIX4项目中需要为非国标清单进行匹配,用户自定义匹配规则。规则可以被存储到数据库中,下次重复使用...

1765
来自专栏web前端教室

重学javascript 红皮高程

最近的先行者计划的学习内容是JS高级程序设计,正好我也跟着再重过一遍JS基础的内容。 这行做到现在,我用JQ,写一般的应用,业务逻辑,插件、组件,只要逻辑清晰写...

1848

扫码关注云+社区