如何减少压栈？

减少递归主要有以下两种方向：

1. 使用循环代替递归；
2. 使用迭代；

以下的例子都以斐波那契数列和阶乘为例。

如果你不懂阶乘，请先看：从阶乘了解数学思维的短板（二）之栈溢出。
如果你不懂斐波那契数列，请先看：从斐波那契数列了解数学思维的短板（一）之重复计算；

循环

所以的递归都可以用循环来实现。

阶乘

const f = (n) => {
    if (n === 0) return 1;
  let result = 1;
  for(let i = 1; i <= n; i += 1) {
      result = i * result;
  }
  return result;
}

斐波那契数列

const fib = (n) => {
    const result = [1, 1];
  for (let i = 2; i <= n; i += 1) {
      result[i] = result[i-1] + result[i-2];
  }
  return result[n];
}

迭代

实现方式：循环和尾递归。
特别的，尾递归是特殊的递归，根据他的 表现形式，我比较倾向把他归为迭代的范畴。
重点：要发现数字、结果等之间的规律。

阶乘

思路：

1. 找规律（上图）；
2. 值 = 上个result * 当前i（0除外）。

循环迭代

const f2 = (n) => {
  if (n === 0) return 1;
    let i = 0, result = 1, next_i, next_result;
  while(i < n){
      next_i = i + 1;
    next_result = result * next_i;
    i = next_i;
    result = next_result;
  }
  return next_result;
}

尾递归迭代

const f4 = (n) => {
  if (n === 0) return 1;
    const ff = (i, n, result) => i === n ?
                                                        result : ff(i + 1, n, (i + 1) * result);
  return ff(1, n, 1);
}

斐波那契数列

已知规律：值等于前两个数相加（0,1除外）。

const fib2 = (n) => {
  if (n === 0) return 1;
  if (n === 1) return 1;
    const fibb = (prev1, prev2, i) => 
              i === n ? prev1 + prev2 
                              : fibb(prev1 + prev2, prev1, i + 1);
  return fibb(1, 1, 2)
}

优化后

const fib3 = (n) => {
  return n === 0 ? 1 
           : n === 1 ? 1
           : fibb(1, 1, 2)
    function fibb(prev1, prev2, i) {
      return i === n ? prev1 + prev2 
                                 : fibb(prev1 + prev2, prev1, i + 1);
  }
}

图解迭代与递归的区别

迭代

递归

迭代的坏处

虽然迭代在理论上是不需要压栈的，但在实际中还是压了栈（此处针对目前的JavaScript语言）。
有一些语言是支持尾递归优化的（可以消去不必要的压栈），但是JavaScript的V8引擎目前并不支持。
特别的，Safari实现了js的尾递归优化。
**

递归压栈图解

摘自文章：从阶乘了解数学思维的短板（二）之栈溢出
阶乘：（根据我实际在chrome调用，最下面为调用f(5)时的匿名函数）

迭代压栈图解

斐波那契数列：（根据我实际在chrome调用，最下面为调用fib(3)时的匿名函数）

总结

1. 递归需要压栈，而栈的长度是有限制的；
2. 可以用循环代替递归；
3. 可以用迭代代替递归；
4. 迭代可以用循环或者尾递归实现；
5. 迭代理想中不用压栈，实际还是会压栈；
6. 尾递归优化可以消除不必要的压栈；
7. js还没有普及尾递归优化。