JS 尾调用优化 (Tail Call Optimization) (严格模式下有限支持) 与递归优化

好的，各位观众老爷们，今天咱们就来聊聊 JavaScript 里那些个“尾巴”的故事，哦不，是尾调用优化（Tail Call Optimization，简称 TCO）和递归优化。这俩家伙，听起来高大上，实际上就是让咱们的递归函数跑得更快更省内存的秘密武器。不过，在 JavaScript 的世界里，这武器有点“娇气”，得在特定条件下才能发挥威力。

开场白：递归的诱惑与困境

先说说递归，这玩意儿就像套娃，一个函数调用自己，一层套一层，直到满足某个条件才停止。写起来简洁优雅，解决某些问题简直是神器。

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

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

上面这段代码计算阶乘，简单明了。但是！问题来了。每调用一次 factorial，JavaScript 引擎都得在内存里开辟一块空间，记录当前函数的上下文（参数、局部变量、返回地址等等）。如果 n 很大，调用次数太多，内存就会爆掉，这就是所谓的“栈溢出（Stack Overflow）”。

尾调用：拯救递归的希望之光

这时候，尾调用优化就该闪亮登场了。啥是尾调用？简单来说，如果一个函数的最后一个动作是调用另一个函数（而不是做其他运算再返回），那么这个调用就叫做尾调用。

举个栗子：

function f(x) {
  return g(x); // 尾调用
}

function f2(x) {
  return g(x) + 1; // 不是尾调用，因为在调用 g(x) 后还有 + 1 操作
}

function f3(x) {
  let y = g(x);
  return y; // 不是尾调用，虽然最后返回了 g(x) 的结果，但中间有个赋值操作
}

尾调用之所以特殊，是因为 JavaScript 引擎可以聪明地重用当前函数的调用栈。也就是说，不用为 g(x) 重新开辟一块内存，直接覆盖 f(x) 的上下文就行了。这样，即使递归调用很多次，也不会导致栈溢出。

尾递归：尾调用的升级版

尾递归就是尾调用的一种特殊情况，指的是一个函数在其尾部调用自身。

function factorialTail(n, acc = 1) {
  if (n === 0) {
    return acc;
  } else {
    return factorialTail(n - 1, n * acc); // 尾递归
  }
}

console.log(factorialTail(5)); // 输出：120

注意看 factorialTail 函数，它在最后一步调用了自身，而且没有做任何额外的运算。这个 acc 参数用来保存中间结果，避免了每次递归都重新计算。

理想很丰满，现实很骨感：TCO 在 JavaScript 中的限制

理论上，只要是尾递归，JavaScript 引擎就可以进行优化，避免栈溢出。但是！在现实中，JavaScript 对 TCO 的支持非常有限。主要原因是为了兼容一些旧的代码和特性，以及调试的方便。

具体来说，只有在严格模式下，并且满足以下条件，TCO 才可能生效：

严格模式： 必须使用 "use strict"; 声明。
尾调用： 必须是真正的尾调用，不能有任何额外的操作。
非闭包： 尾调用函数不能引用当前函数的自由变量。（可以理解为不能形成闭包）

为什么要有这些限制？

严格模式： 严格模式下，函数调用方式更加规范，引擎更容易判断是否是尾调用。
非闭包： 闭包会引用当前函数的变量，如果进行 TCO，当前函数的上下文被覆盖，闭包就无法正常工作了。

代码示例：验证 TCO 是否生效

为了验证 TCO 是否生效，我们可以写一段代码，故意让它递归调用很多次，如果栈溢出，说明 TCO 没有生效；如果没有溢出，说明 TCO 生效了。

"use strict";

function sum(n, acc = 0) {
  if (n === 0) {
    return acc;
  } else {
    return sum(n - 1, acc + n); // 尾递归
  }
}

try {
  console.log(sum(100000)); // 如果 TCO 生效，应该能正常输出结果，否则会栈溢出
} catch (e) {
  console.error("栈溢出啦！", e);
}

在不同的 JavaScript 引擎和环境下，这段代码的结果可能会不同。有些引擎可能支持 TCO，有些则不支持。

表格总结：TCO 的条件与限制

特性	要求	说明
模式	严格模式 (`"use strict";`)	必须开启严格模式，否则 TCO 不会生效。
调用类型	尾调用	函数的最后一个动作必须是调用另一个函数（或自身）。不能有任何额外的操作，比如加减乘除、赋值等等。
闭包	不能形成闭包	尾调用函数不能引用当前函数的自由变量。如果形成了闭包，TCO 会导致闭包无法正常工作。
引擎支持	引擎实现 TCO	即使满足了以上条件，也需要 JavaScript 引擎本身支持 TCO。不同的引擎对 TCO 的支持程度不同。
调试	部分引擎为了调试方便，会禁用 TCO	一些 JavaScript 引擎在调试模式下可能会禁用 TCO，以便开发者能够更好地追踪函数调用栈。

绕过限制：手动优化递归

既然 TCO 的支持有限，我们还可以通过一些手动的方式来优化递归函数，避免栈溢出。

循环代替递归： 对于一些简单的递归，可以用循环来代替。循环没有调用栈的限制，可以避免栈溢出。

function factorialLoop(n) {
  let result = 1;
  for (let i = 1; i <= n; i++) {
    result *= i;
  }
  return result;
}

console.log(factorialLoop(5)); // 输出：120

蹦床函数（Trampoline）： 蹦床函数是一种技巧，可以将递归函数转换成循环，避免栈溢出。

function trampoline(f) {
  while (typeof f === 'function') {
    f = f();
  }
  return f;
}

function sumTail(n, acc = 0) {
  if (n === 0) {
    return acc;
  } else {
    return () => sumTail(n - 1, acc + n); // 返回一个函数
  }
}

const sumTrampoline = trampoline(sumTail(100000));
console.log(sumTrampoline); // 输出：5000050000

蹦床函数的原理是，将递归调用改成返回一个函数，然后用 trampoline 函数循环执行这些函数，直到返回最终结果。这样，每次执行的都是一个新的函数，而不是递归调用，避免了栈溢出。

Continuation Passing Style (CPS)： CPS 是一种编程风格，将函数的返回值传递给一个回调函数（continuation），而不是直接返回。

function factorialCPS(n, continuation) {
  if (n === 0) {
    continuation(1);
  } else {
    factorialCPS(n - 1, function(result) {
      continuation(n * result);
    });
  }
}

factorialCPS(5, function(result) {
  console.log(result); // 输出：120
});

CPS 的原理是，将函数的控制权交给回调函数，避免了递归调用栈的积累。

总结：拥抱递归，但要谨慎

递归是一种强大的编程技巧，可以简化代码，解决复杂问题。但是，递归也有其局限性，容易导致栈溢出。

了解尾调用优化（TCO）的原理和限制，尽量写出符合 TCO 条件的递归函数。
如果 TCO 不生效，或者无法满足 TCO 的条件，可以考虑使用循环、蹦床函数或 CPS 等技巧来优化递归函数。
在实际开发中，要根据具体情况选择合适的递归优化方案。

最后的忠告：

JavaScript 的 TCO 就像一个薛定谔的猫，你永远不知道它是否真的生效了。所以，最好的办法是谨慎使用递归，尽量避免过深的调用栈。如果真的需要用到递归，一定要做好充分的测试和优化，确保代码的健壮性和性能。

好了，今天的讲座就到这里。希望大家对 JavaScript 的尾调用优化和递归优化有了更深入的了解。下次再见！

发表回复 取消回复

发表回复取消回复