js解决递归函数超出调用栈最大次数问题

我们定义一个求和的递归函数，用y来计数，正常情况下，如果传参sum（1,1000），是可以输出1001的，但是当计数次数超过一定范围时，如10000000，就会报错。

            function sum(x,y){
    if(y>0){
     return sum(x+1,y-1)
    }else{
     return x
    }
   }
   var a=sum(1,100000)
   console.log(a)

解决递归次数过大造成的问题，它的原理非常简单。递归之所以需要优化，原因是调用栈太多，造成溢出，那么只要减少调用栈，就不会溢出。怎么做可以减少调用栈呢？就是采用“循环”换掉“递归”。trampoline成为蹦床函数。

方式1：

         function trampoline(f){
    while(f && f instanceof Function){
     f=f() // 返回一个函数，然后执行该函数
    }
    return f
   }
   function sum1(x,y){
    if(y>0){
     return sum1.bind(null,x+1,y-1) // 每次返回函数的另外一个版本
    }else{
     return x
    }
   }
   var b=trampoline(sum1(1,100000))
   console.log(b) // 100001

方式二：

function tco(f) {
  var value;
  var active = false;
  var accumulated = [];

  return function accumulator() {
    accumulated.push(arguments);
    if (!active) {
      active = true;
      while (accumulated.length) {
        value = f.apply(this, accumulated.shift());
      }
      active = false;
      return value;
    }
  };
}

var sum = tco(function(x, y) {
  if (y > 0) {
    return sum(x + 1, y - 1)
  }
  else {
    return x
  }
});

sum(1, 100000)
// 100001

上面代码中，tco函数是尾递归优化的实现，它的奥妙就在于状态变量active。默认情况下，这个变量是不激活的。一旦进入尾递归优化的过程，这个变量就激活了。然后，每一轮递归sum返回的都是undefined，所以就避免了递归执行；而accumulated数组存放每一轮sum执行的参数，总是有值的，这就保证了accumulator函数内部的while循环总是会执行。这样就很巧妙地将“递归”改成了“循环”，而后一轮的参数会取代前一轮的参数，保证了调用栈只有一层。

利用递归求1到n之间的累加：

function getSum(n){
 if(n == 1){
  return 1;
 }
 return getSum(n-1) +n;
}

//类似求整数n的阶乘
getSum(5)  // 1+2+3+4+5