javascript - 为什么使用尾递归也会爆栈？

Question

普通fibonacci：

<code>
        function fibonacci(n) {
            return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
        }</code>

调用栈应该是这样,第 5 项调用栈长度就有 8 了，很容易长度很大造成栈溢出：

<code>[fibonacci(5)]
    [fibonacci(4) + fibonacci(3)]
    [(fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))]
    [((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))) + ((fibonacci(1) + fibonacci(0)) + fibonacci(1))]
    [fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(0) + fibonacci(1)]</code>

改为尾递归方式

<code>function fibonacci2(n) {
        var a = arguments.length > 1 && arguments[1] !== undefined ? arguments[1] : 0;
        var b = arguments.length > 2 && arguments[2] !== undefined ? arguments[2] : 1;
        if (n === 0) {
            return a
        }
        return fibonacci2(n - 1, b, a + b);
    }</code>

调用栈应该一直是1个长度，不知道对不对？：

<code>fibonacci2(5) === fibonacci2(5, 0, 1)
    fibonacci2(4, 1, 1)
    fibonacci2(3, 1, 2)
    fibonacci2(2, 2, 3)
    fibonacci2(1, 3, 5)
    fibonacci2(0, 5, 8) => return 5  </code>

但当我调用 fibonacci2(10000) 时还是会报Uncaught RangeError: Maximum call stack size exceeded错误，这是为什么呢？

Answer 1

楼主使用的语言是JS么,如果是那么很遗憾,JS解释器目前还没有实现尾递归优化,虽然ES6规范有提出尾递归优化规范,但是实现的解释器非常的少传送门

再看这个传送门找到tail call这一栏可以具体查看各个环境对尾递归优化的近况

以上回答欠妥,作者后来参考了相关资料和官方文档,发现node版本在有flag情况下已经能够运行尾递归优化之后的代码了

<code>"use strict";
function countTo(n, acc) {
    if(n === 0) {
        return acc;
    }
    return countTo(n - 1, acc + n);
}
console.log(countTo(100000 , 0))</code>

以上述代码为例,在node6.5+版本中使用--harmony-tailcalls关键字可以运行

node --harmony-tailcalls test.js

得到结果是5000050000

Answer 2

js尾递归优化，在ES6的严格模式下才实现。

其他环境下并不会优化尾递归，跟你写不写尾递归没有关系。

你以为这个函数运行一遍就死了，其实他或者他的某些属性还坚挺的活着...