javascript 尾递归优化

JS 中的递归

我们来看一个阶乘的代码

function foo( n ){  if(n <= 1){    return 1;  }  return n * foo( n - 1 );}
foo(5);  // 120

下面分析一下，代码运行过程中,执行上下文栈是怎么变化的

1. 这个代码是在全局作用域中执行的，所以在 foo 函数得到执行之前，上下文栈中就已经被放入了一个全局上下文。之后执行一个函数，生成一个新的执行上下文时，JS 引擎都会将新的上下文 push 到该栈中。如果函数执行完成，JS 引擎会将对应的上下文从上下文栈中弹出

2. 一开始执行 foo 函数的时候，JS 引擎会创建 foo 的执行上下文，将该执行上下文 push 进上下文栈。然后开始执行 foo 中的代码。

现在上下文栈中已经有了两个执行上下文了

3. 在执行到 foo 中代码快结束时，return 表达式中，又调用了 foo 函数。所以又会创建一个新的执行上下文。并且 JS 引擎会把这新的执行上下文 push 到上下文栈中。

现在上下文栈中已经有了三个执行上下文了

4. 开始重复第 3 步的执行。一直到 n<=1，才不会有新的执行上下文产生。

此刻上下文栈中，已经有了 6 个上下文了（包含了全局上下文）

设想一下

1. 如果刚开始调用的时候，传入 n 的初始值为 100，到 n<=1 时，上下文栈中会有几个上下文。101 个。

2. 如果初始值为 1000 呢？到 n<=1 时，会有 1001 个执行上下文

3. 也就是说，传入的初始值越大，执行上下文栈中，就会有越多的执行上下文🥲

4. 对于上下栈，它的空间是有限的，一旦存放的上下文占用内存产出了它的最大内存，就会出现栈溢出。RangeError: Maximum call stack size exceeded
   

5. 而在 chrome 中，不仅会对栈的空间有限制，还会对函数的递归次数有限制

参考视频讲解：进入学习

递归优化

我们来看一个样例代码

function outer() {    return inner();}
outer();

分析一下，这里的上下文栈是怎么变化的

1. 调用 outer 函数的时候，第二个栈帧被推到了栈上。

第一个栈帧是全局上下文

把上下文栈中的一个上下文称作一个栈帧

2. 执行到了 return 语句，必须要计算 inner 调用结果，才能返回值

3. 调用 inner 函数，第三个栈帧被推入到栈上。

4. 执行 inner 函数，将返回值传回到 outer 函数。inner 执行完毕。第三个栈帧被弹出栈

5. outer 函数再返回值。outer 函数执行完毕，第二个栈帧被弹出栈

等等，情况不是一样的么？优化在哪里

1. 在执行到 outer 中的 return 语句的时候，要先计算 inner 函数的值。这时候 JS 引擎发现，把第二个栈帧弹出去也没有关系。因为到时候，直接拿 inner 的返回值返回出去就好了，第二个栈帧就没有必要保存了。

2. 将第二个栈帧弹出

这个时候，栈中只有一个栈帧了--全局上下文

3. 执行到 inner 函数，inner 函数的上下文被 push 到栈中

这个时候，栈中有两个栈帧了

4. 开始执行 inner 函数，计算返回值后，inner 函数执行完毕。inner 的上下文栈帧被弹出栈。

栈中又只剩一个栈帧了--全局上下文

综上，我们可以看出：如果没有优化，没多调用一次嵌套函数，就会多增加一个栈帧；有了优化之后，无论调用多少次嵌套，栈中只会有两个栈帧。这就是 ES6 尾调用优化的关键😄

递归优化的条件

1. 代码在严格模式下执行

2. 外部函数的返回值，是对尾调用函数的调用

3. 尾调用函数返回后，不需要执行额外的逻辑

4. 尾调用函数不是外部函数作用域中自由变量的闭包

下面是《高程》里面的示例，帮助大家理解

// 无优化： 尾调用没有返回function outer(){  inner();}
// 无优化： 尾调用没有直接返回function outer(){  let innerResult = inner();
  return innerResult;}
//无优化： 尾调用返回值后，必须要转型为字符串function outer(){  return inner().toString(); }
// 无优化： 尾调用是一个闭包function outer(){  let foo = 'bar';
  function inner(){ return foo; }
  return inner();}

其实我觉得上面的倒数第二个，它是完全可以尾调用优化的。因为这个计算是不需要外部函数的上下文里面内容支持的。可能是这样的计算必须要在外部函数的上下文中完成吧，咱也不懂。记一下吧。

有哪位同仁能够帮我解答一下我这个问题吗😁

实操一个优化代码

下面是一个普通的求斐波那契数列的函数

function fib( n ){  if( n < 2){    return n;  }
  return fib(n - 1) + fib(n - 2)}

这是一个非常简单的斐波那契数列的函数，可以看到它不符合尾递归的条件。因为返回值的调用函数参与了额外计算

我们来优化一下

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

看，这样是不是就符合尾递归调用函数了

简单讲解一下上面的代码

1. 把原先的一个函数拆成了两个

2. 第一个函数接受一个参数。这个参数表示求第几位的斐波那契数。

3. 第二个参数接收三个参数。前两个参数表示正在计算的两个位置的数字，第三个参数表示还要计算多少次

斐波那契数规律，就是从第三位开始，每一位的数字都是前两位数字的和

那上面的计算的阶乘代码怎么优化呢？

function foo( n ){  if(n <= 1){    return 1;  }  return n * foo( n - 1 );}
foo(5);  // 120

这个是上面计算阶乘的代码，我们可以用同样的思路，来对其做尾递归函数优化

function foo( n ){  return inner(n, n - 1)}
function inner(sum, n){  if(n <= 1){    return sum；    }  return inner(sum * n , n -1);}
foo(5);

是不是超简单😁

最新版的浏览器已经支持尾递归

可以在计算斐波那契数列的时候，比较尾递归和非尾递归的时间。相信你会和我一样，会不由自主的感叹

总结

1. JS 中的递归函数调用的时候，上下文栈是怎么变化的

2. 什么是递归优化

3. 递归优化的条件是什么

4. 手动优化一个递归代码