JavaScript内核与高级编程之：`JavaScript`的`Tail Call Optimization`：其在递归中的应用。

JavaScript 尾调用优化：拯救递归于水火！

各位观众，晚上好！我是今晚的主讲人，咱们今天来聊聊一个听起来高大上，但其实特别接地气的 JavaScript 话题：尾调用优化 (Tail Call Optimization, TCO)。

别被“优化”两个字吓到，这玩意儿其实就是个“救命稻草”，尤其是在咱们用递归用得嗨皮的时候。很多时候，你写的递归函数，看着简洁优雅，跑起来却分分钟爆栈，这时候，TCO 就像一个默默守护你的超级英雄，在背后默默地帮你优化，让你写的递归函数也能像循环一样流畅。

1. 什么是尾调用？

要理解尾调用优化，首先得搞明白什么是尾调用。简单来说，尾调用就是函数里最后一步是调用另一个函数。注意，是最后一步！

举几个例子：

// 这是一个尾调用
function funcA() {
  return funcB(); // 最后一步是调用 funcB
}

// 这也是一个尾调用
function funcC() {
  let x = 10;
  return funcD(x); // 最后一步是调用 funcD，即使传了参数
}

// 这就不是尾调用！
function funcE() {
  let result = funcF();
  return result + 1; // 最后一步是加 1，不是调用函数
}

// 这也不是尾调用！
function funcG() {
  return 1 + funcH(); // 最后一步是加 1，不是调用函数
}

// 这更不是尾调用！
function funcI() {
  return funcJ() + funcK(); // 最后一步是加法，不是调用函数
}

// 这种形式的也不是尾调用，虽然funcL在最后一行,但return语句里有运算
function funcK() {
  return 1 * funcL();
}

// 这也不是尾调用，因为调用funcM后还有操作（虽然是隐式的）
function funcN(){
  try {
    funcM()
  } catch (e) {
      console.log(e)
  }
}

记住，尾调用必须是函数执行的最后一步，并且直接返回另一个函数的结果。 没有任何其他的计算、操作或者赋值。

2. 为什么需要尾调用优化？

理解了尾调用，我们来谈谈为什么需要尾调用优化。这跟递归有关。

递归是一种函数自己调用自己的编程技巧。它能把复杂的问题分解成更小的、相似的子问题，直到达到一个简单的基础情况，然后逐层返回结果。

听起来很美，但递归有个致命的弱点：每次递归调用，都会在调用栈上创建一个新的栈帧。 栈帧里保存着当前函数的状态（比如局部变量、返回地址等等）。如果递归调用的层数太多，调用栈就会溢出，导致程序崩溃，也就是我们常说的 "Stack Overflow" 错误。

想象一下，你叠了一摞盘子，每递归一次，就往上加一个盘子。盘子叠得太高，就塌了。

// 一个简单的递归函数，计算阶乘
function factorial(n) {
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n - 1); // 不是尾调用！
  }
}

console.log(factorial(5)); // 输出 120

上面的 factorial 函数不是尾调用，因为在递归调用 factorial(n - 1) 之后，还需要将结果乘以 n。这意味着每次递归，都会在调用栈上创建一个新的栈帧，保存 n 的值，等着递归返回结果后进行乘法运算。

如果 n 很大，比如 factorial(10000)，那调用栈就会爆掉。

尾调用优化 (TCO) 的作用就在于：如果一个函数是尾调用，那么引擎（比如 JavaScript 引擎）就可以优化它的执行方式，不创建新的栈帧，而是直接用当前的栈帧来执行新的函数。 这样，无论递归多少层，调用栈都不会溢出。就像你叠盘子的时候，不是往上加盘子，而是把当前盘子里的东西倒到下一个盘子里，然后把当前盘子扔掉。

3. 尾调用优化是怎么工作的？

尾调用优化的核心思想是：重复利用栈帧。

当引擎检测到一个尾调用时，它会做以下几件事：

1. 替换当前栈帧： 将当前栈帧中的局部变量、返回地址等信息替换成被调用函数的信息。
2. 跳转到被调用函数： 直接跳转到被调用函数的入口点，开始执行。

这样，就相当于在同一个栈帧里执行了多个函数，避免了创建新的栈帧，从而节省了内存空间，防止了栈溢出。

4. 如何写出尾调用优化的递归函数？

要让你的递归函数能够被尾调用优化，你需要确保它是尾递归，也就是递归调用发生在函数的最后一步，并且没有任何其他的操作。

我们来改造一下上面的 factorial 函数，使它变成尾递归：

// 尾递归版本的阶乘函数
function factorial(n, accumulator = 1) {
  if (n === 0) {
    return accumulator;
  } else {
    return factorial(n - 1, n * accumulator); // 尾调用！
  }
}

console.log(factorial(5)); // 输出 120

在这个版本中，我们引入了一个 accumulator 参数，用于累积乘积的结果。每次递归调用，都将当前的结果 n * accumulator 传递给下一次递归。这样，递归调用就变成了最后一步，没有任何其他的操作。

关键在于将所有的计算都放在参数里，而不是放在递归调用之后。

再来一个例子，计算斐波那契数列：

// 非尾递归版本的斐波那契数列
function fibonacci(n) {
  if (n <= 1) {
    return n;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2); // 不是尾调用！
  }
}

// 尾递归版本的斐波那契数列
function fibonacci(n, a = 0, b = 1) {
  if (n === 0) {
    return a;
  } else if (n === 1) {
    return b;
  } else {
    return fibonacci(n - 1, b, a + b); // 尾调用！
  }
}

console.log(fibonacci(10)); // 输出 55

同样，我们将所有的计算都放在参数里，确保递归调用是最后一步。

5. 尾调用优化在 JavaScript 中的支持情况

虽然尾调用优化很棒，但可惜的是，JavaScript 对它的支持并不完美。

• ES6 规范： ES6 (ECMAScript 2015) 规范明确要求引擎支持尾调用优化，但实际情况是，各大浏览器厂商的实现并不一致。
• 严格模式： 只有在严格模式下，尾调用优化才会被启用。因为非严格模式下，函数可以访问 arguments 对象和 caller 属性，这会阻止尾调用优化。
• 引擎支持： 截至目前，只有 Safari 浏览器对尾调用优化有较好的支持。Chrome、Firefox 等浏览器虽然也在尝试支持，但效果并不理想。

这意味着，即使你写出了尾递归函数，也不一定能保证它会被优化。

如何开启严格模式：

"use strict"; // 在脚本或函数的开头添加这行代码

function myFunc() {
  "use strict"; // 也可以在函数内部开启严格模式
  // ...
}

6. 尾调用优化实战：一个更复杂的例子

咱们来看一个更复杂的例子：深度优先搜索 (Depth-First Search, DFS) 遍历树结构。

// 树的节点
class Node {
  constructor(value) {
    this.value = value;
    this.children = [];
  }

  addChild(node) {
    this.children.push(node);
  }
}

// 非尾递归的深度优先搜索
function dfs(node, callback) {
  callback(node.value);
  for (let i = 0; i < node.children.length; i++) {
    dfs(node.children[i], callback); // 不是尾调用！
  }
}

// 尾递归的深度优先搜索
function dfs(node, callback, stack = [node]) {
  if (stack.length === 0) {
    return;
  }

  const currentNode = stack.pop();
  callback(currentNode.value);

  const children = currentNode.children;
  for (let i = children.length - 1; i >= 0; i--) { // 倒序入栈，保证遍历顺序
    stack.push(children[i]);
  }

  return dfs(node, callback, stack); // 尾调用！
}

// 创建一个树
const root = new Node("A");
const b = new Node("B");
const c = new Node("C");
const d = new Node("D");
const e = new Node("E");
const f = new Node("F");

root.addChild(b);
root.addChild(c);
b.addChild(d);
b.addChild(e);
c.addChild(f);

// 使用深度优先搜索遍历树
dfs(root, (value) => {
  console.log(value); // 输出 A B D E C F
});

在这个例子中，我们将非尾递归的 DFS 转换成了尾递归的 DFS，通过维护一个栈 stack 来模拟递归调用，确保递归调用是最后一步。

7. 尾调用优化的局限性

虽然尾调用优化很强大，但它也有一些局限性：

• 严格模式： 必须在严格模式下才能启用。
• 引擎支持： 不同引擎的支持程度不一致。
• 代码可读性： 为了实现尾递归，有时候需要改变代码的结构，可能会降低代码的可读性。

8. 总结

尾调用优化是一种强大的优化技术，可以避免递归调用导致的栈溢出。虽然 JavaScript 对它的支持并不完美，但了解它的原理和使用方法，仍然可以帮助我们写出更高效、更健壮的代码。

表格总结：

特性	尾调用	非尾调用
定义	函数执行的最后一步是调用另一个函数	函数执行的最后一步不是调用另一个函数
优点	可以被尾调用优化，避免栈溢出
缺点	需要特定的代码结构，可能降低可读性	容易导致栈溢出
JavaScript支持	严格模式下，部分引擎支持
适用场景	需要进行大量递归调用的场景
示例	return funcB();	return funcB() + 1;
	return funcC(x);	let result = funcF(); return result + 1;

记住以下几点：

• 尾调用是函数执行的最后一步是调用另一个函数。
• 尾调用优化可以避免递归调用导致的栈溢出。
• 只有在严格模式下，尾调用优化才会被启用。
• 为了实现尾递归，可能需要改变代码的结构。

希望今天的讲座能帮助大家更好地理解 JavaScript 的尾调用优化。谢谢大家！下课！