JavaScript代码出现栈溢出之尾调用优化

说栈溢出之前，我们先来一起学习下调用栈，为什么了

什么是 javascript 调用栈

javascript 引擎是利用栈的这种数据结构来管理执行上下文的。在执行上下文创建好后，javascript 引擎会将执行上下文数据压入栈中，通常把这种用来管理执行上下文件的栈称为执行上下文栈，又称调用栈。

• 可以帮助了解 javascript 引擎的工作原理
• 更好的调试 javascript

比如你在开发代码时，有时候可能会遇到栈溢出的错误，如下图所示：

function runStack(n, result) {
  if (n === 0) return result;
  return runStack(n - 2, result);
}
runStack(50000, 100)

为什么会出现这种错误呢？这就涉及到了调用栈的内容，在 javascript 编程中，经常会出现在一个函数中调用另外一个函数的情况，调用栈就是用来管理函数调用关系的一种数据结构。

首先来说说什么栈结构：

栈结构，可以结合一个贴切的例子来理解，一条单车道的单行线，一端被堵住了，而另一端入口处没有任何提示信息，堵住之后就只能后进去的车子先出来，这时堵住的单行线就可以看作一个栈容器，车子开时单行线叫做入栈，车子倒出去叫做出栈。

在车流量较大的场景中，就会发生反复的入栈、栈满、出栈、空栈和再次入栈，一直循环。

同理栈满了就会出栈溢出，上面提到的错误。

在开发中，如何利用好调用栈

• 如何利用浏览器查看调用栈的信息

当执行一段复杂的代码时，可能很难从代码文件中分析其调用关系，这时候就可心在需要查看的函数中加入断点，然后执行到该函数，就可以查看该函数的调用栈了。

这里我们拿上面那段代码做个演示，打开“开发者工具”=》“source”，选择 javascript 代码，加上断点，刷新页面。就可以看到 runStack 函数时，执行流程就暂停了，这时可以通过右边的 “call stack“ 来查看当前的调用栈情况，如下图：

从图中可以看出，右边的 “call stack” 下面显示出来了函数的调用关系

栈的最底部是 anonymous，也就是全局的函数入口

中间的 runStack 函数随代码的执行，栈越来越大，就会造成溢出

除了通过断点来查看调用栈，也可以使用 console.trace() 来输出当前函数的调用关系。

尾调用优化

尾调用是函数式编程的一个重要概念，本身非常简单。就是：某个函数的最后一步是调用另一个函数

尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用帧，调用位置、内部变量等信息都不会再用到，只要直接用内层函数的调用帧，取代外层函数的调用帧就好。

注意：只有不再用到外层函数的内部变量，内层函数的调用帧才会取代外层函数的调用帧，否则无法进行”尾调用优化

function animal(des) {
  var name = 'Dog';
  function run(data) {
    return name + data;
  }
  return run(des)
}

因为内层函数 run 用到了外层函数 animal 的内部变量 name。

• 目前自会有Safari浏览器支持尾调用优化，Chrome和Fiefox都不支持
• ES6的尾调用优化只在严格模式下开启，正常模式下是无效的（因为在正常模式下，函数内部有两个变量，可以跟踪函数的调用栈）
  • func.arguments：返回调用时函数的参数
  • func.caller：返回调用当前函数的那个函数
  • 尾调用优化发生时，函数的调用栈会改写，因此上面两个变量就会失真。严格模式下禁用了这两个变量，所以尾调用优化仅在严格模式下生效

尾递归

• 示例：计算阶乘

// 非尾调用 (计算n的阶乘，最多需要保存n个调用记录，复杂度O(n))
function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}
// 尾调用 (只保留一个调用记录，复杂度O（1）)
function factorial(n, total) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

尾递归优化实现

尾递归优化只能在严格模式下生效，正常情况下，或者那些不支持该功能的环境中，可以自己实现尾递归优化

思路：尾递归之所以需要优化，原因是调用栈太多，造成溢出，那么只要减少调用栈，也就不会溢出了。如何减少调用栈？使用”循环“代替递归

蹦床函数（trampoline）可以将递归执行转为循环执行。

function trampoline(f) {
  while(f && f instanceof Function) {
    f = f();
  }
  return f;
}
function runStack(n) {
  if (n === 0) return 100;
  return runStack.bind(null, n - 2);
}
trampoline(runStack(50000))

蹦床函数接收到个函数 f 做为参数，只要 f 执行后，返回一个函数就继续执行。注意，这里是执行返回的函数，而不是函数里边调用函数，这样就避免了递归执行，从而消除了调用栈过大的问题。

蹦床函数其实并不是真正的尾递归优化：

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 runStack = tco(function(n) {
  if (n === 0) return 100;
  return runStack(n - 2)
})
console.log(runStack(50000))