什么是尾调用？

尾调用（Tail Call）是函数式编程的一个重要概念，本身非常简单，一句话就能说清楚，就是指某个函数的最后一步是调用另一个函数。

function f(x){
  return g(x);
}

最后一步调用并不是指在函数的尾部，只要是最后异步操作即可：

function f(x) {
  if (x > 0) {
    return m(x)
  }
  return n(x);
}
// 上面代码中，函数m和n都属于尾调用，因为它们都是函数f的最后一步操作。

值得注意的是，以下三种情况均不是尾调用：

// 情况一
function f(x){
  let y = g(x);
  return y;
}

// 情况二
function f(x){
  return g(x) + 1;
}

// 情况三
function f(x){
  g(x);
}

上面代码中，情况一是调用函数g之后，还有赋值操作，所以不属于尾调用，即使语义完全一样。情况二也属于调用后还有操作，即使写在一行内。情况三等同于调用g(x)后return undefined。

尾调用优化

尾调用之所以与其他调用不同，就在于它的特殊的调用位置。

下面是重点请仔细阅读:
函数调用会在内存形成一个“调用记录”，又称“调用帧”（call frame），保存调用位置和内部变量等信息。如果在函数A的内部调用函数B，那么在A的调用帧上方，还会形成一个B的调用帧。等到B运行结束，将结果返回到A，B的调用帧才会消失。如果函数B内部还调用函数C，那就还有一个C的调用帧，以此类推。所有的调用帧，就形成一个“调用栈”（call stack）。
尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用帧，因为调用位置、内部变量等信息都不会再用到了，只要直接用内层函数的调用帧，取代外层函数的调用帧就可以了。

下面来看一个例子:

function g(item) {
  return item
}
// 下面是尾调用例子
function f() {
  let m = 1
  let n = 2
  return g(m + n)
}
f()
// 上面例子实际上等同于:
g(3)

上面代码中，如果函数g不是尾调用，函数f就需要保存内部变量m和n的值、g的调用位置等信息。但由于调用g之后，函数f就结束了，所以执行到最后一步，完全可以删除f(x)的调用帧，只保留g(3)的调用帧。

这就叫做“尾调用优化”（Tail call optimization），即只保留内层函数(即g函数)的调用帧。如果所有函数都是尾调用，那么完全可以做到每次执行时，调用帧只有一项，这将大大节省内存。这就是“尾调用优化”的意义。
注意，只有不再用到外层函数(函数f)的内部变量，内层函数(函数g)的调用帧才会取代外层函数的调用帧，否则就无法进行“尾调用优化”。

function addOne(a){
  var one = 1;
  function inner(b){
    return b + one;
  }
  return inner(a);
}

显而易见，上面的函数不会进行尾调用优化，因为内层函数inner用到了外层函数addOne的内部变量one。

尾递归是什么？

递归相信大家都听过，函数调用自身，称为递归，如果尾调用自身，就称为尾递归。

递归非常耗费内存，因为需要同时保存成千上百个调用帧，很容易发生“栈溢出”错误（stack overflow）。但对于尾递归来说，由于只存在一个调用帧，所以永远不会发生“栈溢出”错误。

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

factorial(5) // 120

让我们来理一下上面函数的顺序：
进入之后 由于 n !== 1 进入 return n * factorial(n - 1) 即 5 * factorial(4)
第二次进入 n === 4 , return 4 * factorial(3)
知道 n === 1, return 1出来相当于变成了 5 * 4 * 3 * 2 * 1 = 120
上面代码是一个阶乘函数，计算n的阶乘，最多需要保存n个调用记录，复杂度 O(n)(可以理解为调用帧个数) 。

下面是我自己的理解:
通过上面的尾调用概念我们可以知道，n * factorial(n-1)中，第一个n是外层函数的变量，第一个n在这里被公开使用，会使他继续保留外层函数的内存变量信息和调用帧，这样下来就启用了4个调用帧（n===1 时没有启用任何函数的调用帧）。

下面我们用尾调用来改良这个递归函数：

function factorial(n, total) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5, 1) // 120

这里传了两个参数，第二个参数为total,我们来看一下函数的运作：
第一次进入：直接调用 factorial(5-1, 5 * 1) 即 factorial(4, 5)
第二次进入：调用 factorial(4-1, 4 * 5) 即 factorial(3, 20)
第三次进入：调用 factorial(3-1, 3 * 20) 即 factorial(2, 60)
第四次进入：调用 factorial(2-1, 2 * 60) 即 factorial(1, 120)
第五次进入：因为n ===1, 所以 return 120
细心的人可能会发现有个问题，就是我同样再return 中使用了 n 这个变量，
之前不是尾调用的是: return n * factorial(n - 1)
而这次的是 return factorial(n - 1, n * total)
按照官方文档上的只要不再用到外层函数的内部变量，内层函数的调用帧才会取代外层函数的调用帧，否则就无法进行“尾调用优化”
为什么在return factorial(n - 1, n * total)参数中用到了外层函数的n，却做到了尾调用优化呢？

下面是我自己的理解：
在 return n * factorial(n - 1)中，第一个n属于外层函数的变量，在做递归的时候，外层函数就需要保存变量n，和下一个factorial 的调用位置信息，我最后的n === 1，return的值，会一步一步找到我的这个外层函数的变量然后再做乘法运算最后把最终值return出来，所以它既保留了外层函数的变量和调用帧，又保留了内存函数的调用帧，直到最后一步return出来，才销毁所有的调用帧和变量（js回收机制，局部变量调用后被销毁）。
而return factorial(n - 1, n * total)这里只是一个参数的传递，n的值传给下一个factorial作为参数，在外层就已经销毁了，因为已经调用完毕，这个n并不会对以后的运算产生任何影响。作为一个局部变量它会被回收掉，所以这个内层函数它将不再用到外层函数的内部变量，即做到了尾调用优化。

递归函数的改写

尾递归的实现，往往需要改写递归函数，确保最后一步只调用自身。做到这一点的方法，就是把所有用到的内部变量改写成函数的参数。比如上面的例子，阶乘函数 factorial 需要用到一个中间变量total，那就把这个中间变量改写成函数的参数。这样做的缺点就是不太直观，第一眼很难看出来，为什么计算5的阶乘，需要传入两个参数5和1？
这里介绍一种最简单的写法，使用es6函数的默认值：

function factorial(n, total = 1) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5) // 120

值得注意的是：
ES6 的尾调用优化只在严格模式下开启，正常模式是无效的。

这是因为在正常模式下，函数内部有两个变量，可以跟踪函数的调用栈。

• func.arguments：返回调用时函数的参数。
• func.caller：返回调用当前函数的那个函数。
  尾调用优化发生时，函数的调用栈会改写，因此上面两个变量就会失真。严格模式禁用这两个变量，所以尾调用模式仅在严格模式下生效。

尾调用优化的实现

尾递归优化只在严格模式下生效，那么正常模式下，或者那些不支持该功能的环境中，有没有办法也使用尾递归优化呢？回答是可以的，就是自己实现尾递归优化。

它的原理非常简单。尾递归之所以需要优化，原因是调用栈太多，造成溢出，那么只要减少调用栈，就不会溢出。怎么做可以减少调用栈呢？就是采用“循环”换掉“递归”。
下面是一个正常的递归函数。

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

sum(1, 100000)
// Uncaught RangeError: Maximum call stack size exceeded(…)

上面代码中，sum是一个递归函数，参数x是需要累加的值，参数y控制递归次数。一旦指定sum递归 100000 次，就会报错，提示超出调用栈的最大次数。
下面来看尾递归优化后的代码：

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循环总是会执行。这样就很巧妙地将“递归”改成了“循环”，而后一轮的参数会取代前一轮的参数，保证了调用栈只有一层。