尾巴调用优化、尾递归



尾调用

尾调用：指某个函数的最后一步是调用另一个函数

// 函数的最后一步是调用另一个函数
function f(x) {
  return g(x);
}
// 尾调用不一定出现在函数尾部，只要是最后一步操作即可。
function f(x) {
  if (x > 0) {
    return m(x);
  }
  return n(x);
}
// 以下两种情况，都不属于尾调用
function f(x) {
  let y = g(x);
  return y;
}
function f(x) {
  return g(x) + 1;
}



尾调用优化

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

函数调用会在内存形成一个调用记录，又称调用栈，保存调用位置和内部变量等信息

如果在函数 A 内部调用函数 B，那么在 A 的调用记录上方，会形成一个 B 的调用记录。
等到 B 运行结束，将结果返回到 A，B 的调用栈记录才会消失
如果 B 内部还有一个函数 C，那就会有一个 C 的调用记录栈

已此类推，所有的调用记录，就形成了一个”调用栈”（call stack）

尾调用由于是函数最后一部操作，不需要保留调用位置，内部信息等
直接用内层函数的调用记录取代外层函数的调用记录就可以了

尾调用优化（Tail call optimization）只保留内层函数的调用记录
函数都是尾部调用，每次执行调用记录只有一项，可以大大节省内存空间



尾递归

函数调用自身，则称为递归。如果尾调用自身，则称为尾递归

递归非常耗费内存，可能出现成百上千个调用栈记录，很容易发生“栈溢出”错误
对于尾递归来说，只存在一个调用记录，就不会发生“栈溢出”错误

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

factorial(5); // 120

这是一个阶乘函数，计算 n 的阶乘，最多需要保存 n 个调用记录，复杂度 O(n)

如果改成尾递归，只保留一个调用记录，复杂度 O(1)

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

factorial(5, 1); // 120

尾调用优化对递归操作有着重大意义,一些函数式编程语言将其写入了语言规格
ES6 也是如此



尾递归

尾递归的实现，往往需要改写递归函数。确保最后一部只调用自身
做到这一点的方法，就是把所有用到的内部变量改写成函数的参数

如上面的例子，阶乘函数 factorial 需要拥戴一个中间变量 total,就把中间变量改写成函数参数
这样做的缺点是不太直观，第一眼很难看出来

可以通过在尾调用函数之外，再提供一个正常形式的函数

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

function factorial(n) {
  return tailFactorial(n, 1);
}

factorial(5); // 120

上面代码通过一个正常形式的阶乘函数 factorial,调用尾递归函数 tailFactorial。看上去稍微正常些了

还有一种方式是利用 ES6 函数参数默认值

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

factorial(5); // 120



参见