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

问题描述

问 题

普通fibonacci：

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

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

[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)]

改为尾递归方式

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

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

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  

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

解决方案

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

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

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

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

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

node --harmony-tailcalls test.js

得到结果是5000050000

这篇关于javascript - 为什么使用尾递归也会爆栈？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！