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

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

优化

我在用递归写斐波那契数列时，当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里没生效？应该用什么方法才能处理大数值的斐波那契计算？

我来解答赞 3 收藏

反馈

1 条解答

云超 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