尾调用优化和尾递归

理解尾调用优化原理，用尾递归避免栈溢出

问题

什么是尾调用优化和尾递归？如何利用它们优化递归函数？

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

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

以下情况不属于尾调用：

// 情况一：调用后还有赋值操作
function f(x) {
  let y = g(x);
  return y;
}

// 情况二：调用后还有计算操作
function f(x) {
  return g(x) + 1;
}

尾调用不一定出现在函数末尾，只要是最后一步操作即可：

function f(x) {
  if (x > 0) {
    return m(x); // 尾调用
  }
  return n(x); // 尾调用
}

函数调用会在内存中形成调用帧（call frame），保存调用位置和内部变量等信息。多个函数调用会形成调用栈（call stack）。

尾调用由于是函数的最后一步操作，外层函数的调用位置和内部变量都不会再用到，因此可以直接用内层函数的调用帧取代外层函数的调用帧。

function f() {
  let m = 1;
  let n = 2;
  return g(m + n);
}
f();

// 等同于
function f() {
  return g(3);
}
f();

由于调用 g 之后函数 f 就结束了，可以删除 f() 的调用帧，只保留 g(3) 的调用帧。这就是尾调用优化，能大大节省内存。

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

普通递归会保存大量调用帧，容易发生栈溢出：

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

factorial(5); // 120

这个阶乘函数最多需要保存 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 规定所有实现都必须部署尾调用优化。使用尾递归可以避免栈溢出，节省内存。