什么是尾递归优化-一一网

（各位大佬，觉得我写的还算认真的话，可不可以点个赞，跪谢！！）

在 ES 6 之前，就算我们递归函数写的没问题，但是也会因为浏览器对调用栈大小的限制，出现栈溢出（ stack overflow）的问题。

后来在 ES 6 的规范中就增加了一项内存优化机制，让 JS 引擎在满足条件的时候可以重用栈帧。也叫做「尾调用优化」。如果这项技术使用到递归函数里，就是我们常提的「尾递归优化」。

那栈帧是什么呢？它属于调用栈，对应着一个未运行完的函数。同时，栈帧中保存了该函数的返回地址和局部变量。重用栈帧意味着两个函数先后用到了相同的那个栈帧。那重用栈帧有什么好处呢？它不仅让函数的运行速度更快了，还让内存更节省了。

其实并不是只有递归函数才能只有享受到这个优化的红利，只不过这个优化在使用递归函数的时候效果特别明显。

我们举一个不在递归函数中使用的例子：

foo()

function foo() {
    return bar();
}

function bar() {};
复制代码

下面是当前执行环境的调用栈：

上面的那一段代码就能满足重用栈帧的情况，也就是说 foo 和 bar 重用了一个栈帧。有一点注意：Call Stack 并不能把重用栈帧的这种情况表示出来，它更多的强调了调用的顺序，重用的栈帧数目并不能和浏览器的 Call Stack 里的展示的函数数目划等号。

对于上面那段代码来说，如果不能重用栈帧，执行的流程将是下面这样的：

准备执行 foo 函数，产生了一个栈帧，入栈，
开始执行 foo
执行 return 语句
发现 return 的结果是一个函数，为了执行 bar，又产生了一个栈帧，入栈
执行 bar 函数体，并返回，bar 的栈帧出栈。
foo 函数拿到返回结果后再返回，foo 的栈帧，出栈

可以看到，我们用到了两个栈帧。

如果可以重用栈帧的话，会变成下面这样：

准备执行 foo 函数，产生了一个 foo 的栈帧，
开始执行 foo
执行到 return 语句，此时发现将 foo 的栈帧弹出也没有影响，弹出 foo 的栈帧
return 的结果是一个函数，为了执行 bar，产生一个 bar 的栈帧，入栈。
执行 bar 并计算返回值
bar 的栈帧出栈。

我们发现，整个过程，就在调用栈里用到了一个栈帧。

那满足什么条件，才能重用栈帧的条件呢？

外部函数的返回值是对尾调用函数的调用，也就是返回值是执行一个函数。
尾调用函数返回后不需要进行额外的逻辑。下面这个例子就是不行的，因为还需要外部函数的执行环境，JS 引擎就不能提前弹出外部函数的栈帧了。

foo()

function foo() {
    return bar() + 1; // 不行
}

function bar() {};
复制代码

尾调用函数内部没有因为引用外部函数的变量而形成一个闭包，这样也不能提前弹出外部函数的栈帧了，比如下面这样：

foo()

function foo() {
    let a = 1;
    return bar(); // 不行
}

function bar() {
    return a;
};
复制代码

了解了重用栈帧的条件，我们再来看一个经典的例子 —— 斐波那契数列，看它如何利用「尾递归优化」。

这道题目经常被用来教学递归，但是在 Leetcode 等平台上，使用循环的做法才是标准解法。

使用递归的解法如下，这样会爆栈：

function fib(n) {
    if (n === 1) {
        return 1;
    } else if (n === 0) {
        return 0;
    }
    
    return fib(n-1) + fib(n-2); 
}
复制代码

现在有了尾递归优化，稍作改动，我们使用递归也可以在实现了尾递归优化的 JS 引擎上比较高效的做到这件事。

直接写出递归优化的版本可能不会很直观，我们一步一步的来。

我们先写一个最直观的一个版本：

function fib(n) {  
   let memo = [0, 1];
   let i = 2;
    
   while(i <= n) {
        memo[i] = memo[i-1] + memo[i - 2];
        i++;
    } 
    
    return memo[n];
}
复制代码

在这个基础上，我们发现 memo 数组可以不要，再优化一版：

function fib(n) {  
   if (n == 0) {
       return 0;
   }
   let a = 0; //  相当于 memo[i-2]
   let b = 1; // 相当于 memo[i-1]
   let sum = 0; // 相当于 memo[i]
   let i = 2;
    
   while(i <= n) {
        sum = a + b; 
        a = b; 
        b = sum;
        i++;
    } 
    
    return sum;
}
复制代码

理解了上面那个版本，稍微改变一下 a、b、sum 的语义也是可以的：

function fib(n) {  
   let a = 0; //  相当于 memo[i]
   let b = 1; // 相当于 memo[i+1]
   let sum = 0; 
   let i = 0;
    
   while(i < n) {
        sum = a + b; 
        a = b; 
        b = sum;
        i++;
    } 
    
    return a;
}
复制代码

最后，在理解了上面代码的基础上，顺着这个思路，我们尝试把他改成递归版：

function fib(n) {  
    return fibInner(0, 1, n); 
}

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

复制代码