javascript - 关于尾递归优化的问题

Question

在js函数式编程中由一个尾递归的问题。http://es6.ruanyifeng.com/#do...尾调用优化

function fibonacciTail(n, a = 0, b = 1) {  
  if (n === 0) return a
  return fibonacciTail(n - 1, b, a + b)
}

可以是实现尾递归优化的一个典型例子，在这里，每次调用后递归传入 fibonacciTail 函数的 n 会依次递减 1，它实际上是用来记录递归剩余的次数。而 a 和 b 两个参数在每次递归时也会在计算后再次传入 fibonacciTail 函数，写成调用栈的形式就很清楚了：

fibonacciTail(5) === fibonacciTail(5, 0, 1)  
fibonacciTail(4, 1, 1)  
fibonacciTail(3, 1, 2)  
fibonacciTail(2, 2, 3)  
fibonacciTail(1, 3, 5)  
fibonacciTail(0, 5, 8) => return 5

可以看到，每次递归都不会增加调用栈的长度，只是更新当前的堆栈帧而已。也就避免了内存的浪费和爆栈的危险。(以上是摘抄的)
同样类似的一个例子

function sum(x, y) {
  if (y > 0) {
    return sum(x + 1, y - 1);
  } else {
    return x;
  }
}

sum(1, 100000)

为什么会爆栈呢？为什么不可以类推成

sum(1,10000) 
sum(2,9999)
sum(3,9998)
...
sum(10000,1)
sum(10001,0) =>return 10001

这个函数内部函数并未引用外层函数的内部变量，两个变量x,y均为引用外部变量。 问题的关键难道是 return x返回的不是一个尾调函数么？

Answer 1

其他答案说得对，你需要用use strict才会触发tail call optimization，否则解释器不能识别出是尾递归，还是会把状态压到栈上

如果你不想用use strict，而且坚持要用递归的话，就需要将状态保存到闭包里，
你得用Trampoline技法改写尾递归，让sum显式地弹出下一次执行的函数让trampoline来运行:

function trampoline(kont)
{
    while(typeof kont == "function")
        kont = kont();
    return kont;
}

function sum(x, y) 
{
    _sum = (x, y) => y > 0 ? () => _sum(x + 1, y - 1) : x // 改写后的尾递归
    
    return trampoline( _sum(x, y) );
}

然后运行sum(1, 100000)就能迅速得到100001的结果

更详细的解释可以看我的博文基于CPS变换的尾递归转换算法

Answer 2

代码应该没问题，fibonacciTail(100000)目测也会溢出，尾优化好像要使用严格模式。
试试看！

Answer 3

“尾递归”顾名思义需要递归步骤在函数的尾部。试试下面的写法：

function sum(x, y) {
  if (y === 0) return x
  return sum(x + 1, y - 1)
}

Answer 4

首先，尾调用需要严格模式。所以函数应改写为

function sum(x, y) {
  'use strict';
  if (y > 0) {
    return sum(x + 1, y - 1);
  } else {
    return x;
  }
}

sum(1, 100000)

其次现在浏览器默认都没有开启尾调用，至于原因，Chrome团队在这篇blog里有讲述，对于最新版的Chrome 55，需要开启chrome://flags/#enable-javascript-harmony 实验性的Javascript功能。
对于node.js 6.9版本，需要开启 --harmony-tailcalls 参数。
上面的代码即可正常运行出结果。

Answer 5

es5并不支持尾递归优化，也许只有跑在node环境下或者V8引擎才会有优化机制，但是一般不建议使用递归，斐波那契数列的话完全可以不是用递归就能够解出来

{
        var res = [1,2];
        for(var i=2;i<n;i++){  
            res[i] = res[i-1] + res[i-2];  
        }  
        return res[n-1];
}