递归计算斐波那契数列时为什么会出现栈溢出？

慕容瑞红提问于 2026-02-13 23:39:27 阅读 35

优化

我在用递归写斐波那契数列时，当n超过1000就会报错“Maximum call stack size exceeded”。尝试把代码改成尾递归形式后还是不行，难道不是尾递归优化能解决吗？

我的代码是这样的：function fib(n) { return n < 2 ? n : fib(n-1) + fib(n-2) }，当n很大时直接崩了。我查资料改成尾递归版本：


function fib(n) {
  function helper(a, b, count) {
    return count === 0 ? b : helper(b, a + b, count - 1);
  }
  return helper(1, 1, n - 1);
}

结果发现当n=1e5时依然报同样的错，这说明尾递归优化在JavaScript里没生效？应该用什么方法才能处理大数值的斐波那契计算？

我来解答赞 9 收藏

反馈

2 条解答

爱豪 Lv1

我之前踩过这个坑，真不是你写错了，是 JavaScript 引擎压根没做尾递归优化（TC39 那帮人一直没定稿，主流引擎比如 V8、SpiderMonkey 都没实现 TCO），你写成尾递归形式，它还是老老实实堆栈增长，n 一大会直接爆掉。

你第一个写法 fib(n-1) + fib(n-2) 是指数级调用，n=50 就卡死了，n=1000 根本不用想；你第二个尾递归版本虽然时间复杂度降成 O(n) 了，但每调一次 helper 就压一层栈，n=1e5 就是 10 万层调用，栈空间早炸了。

要解决这个问题，直接别用递归了，改迭代就行，栈空间 O(1)，速度还快：

function fib(n) {

  if (n < 2) return n;

  let a = 0, b = 1;

  for (let i = 2; i <= n; i++) {

    const c = a + b;

    a = b;

    b = c;

  }

  return b;

}

不过要注意，n 大了之后结果会超出 Number 的安全整数范围（Number.MAX_SAFE_INTEGER 是 2^53-1），比如 n=78 就开始溢出了，这时候得用 BigInt：

function fibBig(n) {

  if (n < 2) return BigInt(n);

  let a = 0n, b = 1n;

  for (let i = 2; i <= n; i++) {

    const c = a + b;

    a = b;

    b = c;

  }

  return b;

}

我之前项目里用过这个，n=100000 都没问题，返回个超长的 BigInt 字符串，内存和性能都能扛住。真要算超大 n（比如百万级），就得用矩阵快速幂或者快速倍增法（fast doubling）了，不过那是另一层优化了，先从迭代开始吧，别再跟递归较劲了，JS 就不是干这个的料。

2026-02-24 23:13

云超 Lv1

JavaScript引擎确实支持尾递归优化，但大多数浏览器和Node.js环境默认都没开启这个特性，所以你的尾递归代码依然会爆栈。直接用迭代法吧，简单又高效。

function fib(n) {

  if (n < 2) return n;

  let a = 0, b = 1;

  for (let i = 2; i <= n; i++) {

    let temp = a + b;

    a = b;

    b = temp;

  }

  return b;

}

如果非要追求极限性能，可以用矩阵快速幂算法，时间复杂度O(log n)。不过这玩意写起来麻烦，调试也费劲，一般没必要用。

function fib(n) {

  if (n < 2) return n;

  function multiply(a, b) {

    return [

      [a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],

      [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]]

    ];

  }

  function pow(mat, p) {

    let result = [[1, 0], [0, 1]];

    while (p > 0) {

      if (p % 2 === 1) result = multiply(result, mat);

      mat = multiply(mat, mat);

      p = Math.floor(p / 2);

    }

    return result;

  }

  const matrix = [[1, 1], [1, 0]];

  const result = pow(matrix, n - 1);

  return result[0][0];

}

最后提醒一句，大数计算记得用BigInt，不然数字一大就溢出了。改起来也不难，把所有相关变量都加上n后缀就行。

2026-02-14 02:19