在 JS 中，如何解决递归导致栈溢出问题

2024-12-18

907 字约 4 分钟

...

关键词：栈溢出问题

在 JavaScript 中，递归如果执行过深，确实有可能导致“栈溢出(stack overflow)”错误，因为每次函数调用都会向调用栈中添加一个新的帧，而每个线程的调用栈都有其最大容量限制。当这个容量被超过时，就会发生栈溢出。为了解决这个问题，你可以使用几种不同的方法：

尾调用优化（Tail Call Optimization）

在 ES6 中，引入了尾调用优化。这意味着如果函数的最后一个操作是返回另一个函数的调用（即尾调用），那么这个调用可以在不增加新栈帧的情况下执行。但是，截至我知识更新的时间，大多数 JavaScript 引擎还没有实现这项优化，或者它在默认情况下并未激活。

转化为循环

大多数递归函数都可以重写为循环，这样可以避免调用栈问题。这种方法需要手动维护一个栈来存储必要的状态信息，而这个栈通常是存储在堆（heap）中的数组，不受调用栈大小限制。

例如，下面递归计算阶乘的代码：

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

可以重写为循环形式：

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

用 Trampoline 函数

Trampoline 是一个高阶函数，使您可以在递归调用的情况下避免栈溢出。它通过在每个递归步骤返回一个函数而不是值，然后持续调用这些函数，直到获得最终结果为止。

function trampoline(fn) {
  return function (...args) {
    let result = fn.apply(this, args);

    while (typeof result === "function") {
      result = result();
    }

    return result;
  };
}

然后，将原始递归函数改写为每次递归调用返回一个函数：

function recursiveFunction(args) {
  if (baseCase) {
    return finalValue;
  } else {
    return function () {
      return recursiveFunction(newArgs);
    };
  }
}

const trampolinedFunction = trampoline(recursiveFunction);

调用 trampolinedFunction 会避免栈溢出，因为它不是真正的递归调用，只是同步循环调用那些返回的函数。

生成器和 Promises

使用 ES6 的生成器(generator)和/或 Promises 也可以用来避免递归调用过深。这些特性可以帮助您生成异步递归调用，其允许事件循环（event loop）介入，避免单次执行过多递归调用造成的栈溢出。

使用异步递归

将递归函数改造成异步函数（async function），并确保每一次递归调用都有机会返回控制权给 JavaScript 事件循环，这可以通过setTimeout、setImmediate或者process.nextTick（在 Node.js 环境下）实现。

例如，可以将一个同步递归函数改写为：

function recursiveAsyncFunction(i) {
  if (i < 0) return Promise.resolve();
  console.log("Recursion ", i);
  return new Promise((resolve) => {
    setImmediate(() => {
      resolve(recursiveAsyncFunction(i - 1));
    });
  });
}