尾递归优化 - 尾递归优化

原理

调用一个函数时，就会形成一个调用帧；在A函数内部执行B函数：当调用A函数时形成一个A的调用帧，在A函数内部调用B函数，在A调用帧上又会生成B调用帧，B执行完毕时B调用帧消失，A完毕后A调用帧消失；如果B是在A函数最后执行，那么A调用帧就可以直接消失。

function A(){
    function B(){}
    return B(); // 要有return这个才是最后
}

注意一点，这时B函数不能使用A函数内部的变量，下面这个就不行。

function A(){
    let one = 1;
    function B(){
        console.log(one);
    }
    return B(); // 要有return这个才是最后
}

尾递归优化

根据上面的原理，我们就可以使用尾递归来对递归调用进行优化。像求斐波那契数列和求n的阶层，都可以使用尾递归优化。
没有优化的求菲波那切数列

function feib(n){
    if(n<=1){
        return 1
    }
    return feib(n-1) + feib(n-2)
}
console.log(feib(100));

递归非常消耗内存，应为有非常多的调用帧，很容易栈溢出；使用尾递归优化，使得函数只有一个调用帧，就不会栈溢出了：

function feib(n,pre = 1, cur = 1) {
    if (n <= 1) {
        return cur;
    }
    return feib(n-1, cur, cur + pre)
}

目前只有 Safari 浏览器支持尾调用优化，Chrome 和 Firefox 都不支持
这个求菲波那切数列变快的原因还有一个很重要的原因就是思路变化了。之前是求n个要先求n-1和n-2;n-1又要求n-2和n-3;n-2要求n-3和n-4，这里就开始重复求值了；优化后，实际就是按顺序从1+1得到的值递归求feib(n,1,2),这个n就是此时，前一个求得的值给后一个。