为何我的JavaScript递归记忆化函数触发Maximum Call Stack Exceeded错误？

使用递归+记忆化求解斐波那契数列时，输入大数值（如9657），你的实现触发Maximum Call Stack Exceeded错误，但GFG的版本能正常运行。两者仅在计算结果的赋值与返回逻辑上存在细微差异。

你的实现代码 #

function topDown(n) {
  const modulus = 10 ** 9 + 7;
  const dp = {};
  function rec(value) {
    if (value <= 1) {
      return value;
    }
    if (dp[value] !== undefined) {
      return dp[value];
    }
    dp[value] = (rec(value - 1) + rec(value - 2)) % modulus;
    return dp[value];
  }
  return rec(n);
}

GFG的可行实现代码 #

function topDownTwo(n) {
  const modulus = 10 ** 9 + 7;
  const dp = {};
  function rec(value) {
    if (value <= 1) {
      return value;
    }
    if (dp[value] !== undefined) {
      return dp[value];
    }
    const ans = (rec(value - 1) + rec(value - 2)) % modulus;
    dp[value] = ans;
    return ans;
  }
  return rec(n);
}

关键差异：栈帧开销与引擎优化的细微影响 #

两个实现的递归逻辑本质一致，但返回环节的细节导致了栈溢出的差异：

• 你的代码中，计算结果直接赋值给dp[value]，随后通过读取对象属性dp[value]返回。这一步对象属性访问会增加每一层递归栈帧的微小开销。
• GFG的代码先将计算结果存入局部变量ans，赋值给dp[value]后直接返回ans。局部变量的返回操作更简洁，栈帧开销更小。

当n达到9657时，递归栈深度已接近JavaScript引擎的栈大小上限（不同引擎上限不同，通常在几千到几万之间）。你的实现每一层栈帧的额外开销积累后，总栈大小刚好超过限制，触发栈溢出；而GFG的实现因栈帧开销更小，刚好处于栈上限以内。

根本解决方案：避免递归栈深度问题 #

递归+记忆化的斐波那契实现栈深度始终为O(n)，无法从根本上解决大数值的栈溢出问题。更可靠的方案是：

1. 迭代法：用循环代替递归，栈深度始终为O(1)：

function fibIterative(n) {
  const modulus = 10 ** 9 + 7;
  if (n <= 1) return n;
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, (a + b) % modulus];
  }
  return b;
}

2. 尾递归优化写法（仅在支持尾调用优化的环境如严格模式下的Node.js生效）：

'use strict';
function fibTail(n, a = 0, b = 1) {
  const modulus = 10 ** 9 + 7;
  if (n === 0) return a;
  if (n === 1) return b;
  return fibTail(n - 1, b, (a + b) % modulus);
}

内容的提问来源于stack exchange，提问作者Bharadwaj Dasavaram