关于尾递归优化的问题

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

我来回答下当初自己提的这个问题，上次参加杭州 node party的时候， 贺老讲了stc-vs-ptc.总的来说，尾归调用的想法是好的，但是落地的时候出现了分歧，node在后续的版本中支持过尾归调用，但后续给去掉了。浏览器上只有safari支持，而其他浏览器上并不支持。所以，这是一个“未真正实现的提议”，大家仅仅了解下，目前还无法普遍用到生产环境中。

Answer 2

本质上就是把递归变成while循环，简单分析一下:

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

这段代码之后,sum是一个闭包函数.可以等价替换下面的定义:

var sum = function() {
    accumulated.push(arguments);
    if (!active) {
      active = true;
      while (accumulated.length) {
        value = function(x, y) { if (y > 0) { return sum(x + 1, y - 1) } else { return x } }.apply(this, accumulated.shift());
      }
      active = false;
      return value;
    }
  };

函数里面的value, active, accumulated,是闭包形成的私有变量.然后分析一下

sum(1, 100000)

实质上发生了什么.首先accumulated = [{0:1, 1:100000}],然后进入if语句,active = true.然后进入while语句,

value = function(x, y) { if (y > 0) { return sum(x + 1, y - 1) } else { return x } }.apply(this, accumulated.shift());

可以等价替换成

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

又可以等价替换成

value = sum(1+1, 100000 - 1)

此时

accumulated = []
value = undefined
active = true

进入sum(1+1, 100000 - 1)函数后没有进入if循环,返回undefined,但是accumulated = [{0:2, 1:99999}]

所以

value = sum(1+1, 100000 - 1)

又可以等价替换成

value = undefined

但是由于私有变量accumulated有值[{0:2, 1:99999}],所有又进入while循环.以此类推......

Answer 3

其他答案说得对，你需要用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 4

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

Answer 5

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

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

Answer 6

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

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 7

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];
}