在 JS 中, 如何解决递归导致栈溢出问题?【热度: 269】

关键词:栈溢出问题

在 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 事件循环,这可以通过setTimeoutsetImmediate或者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));
    });
  });
}

记得确保递归终止条件是正确的,否则即便以上方法也可能导致无限循环或者内存泄漏。每一种方法都有其适用场景,具体使用哪一种方法取决于问题的具体需求。