JavaScript 递归与栈溢出：原因与解决方案

递归是编程中一种优雅的思维方式，但 JavaScript 的递归容易出现「栈溢出」（Stack Overflow）错误。本文将深入 JavaScript 的调用栈机制，分析栈溢出的原因，并提供多种实用的解决方案。

什么是递归？

递归是指函数直接或间接调用自身的编程技巧。一个正确的递归函数必须包含两个部分：

递归基线条件（Base Case）：终止递归的条件
递归步骤（Recursive Step）：将问题分解为更小的同类问题

// 经典的阶乘函数递归
function factorial(n) {
  // 基线条件：n = 0 或 n = 1 时返回 1
  if (n <= 1) {
    return 1;
  }
  // 递归步骤：n! = n × (n-1)!
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120
<link rel="stylesheet" href="/assets/css/code-blocks.css?v=20261019_04">

递归的执行过程

调用 factorial(5) 时，执行过程如下：

factorial(5)
= 5 × factorial(4)
= 5 × (4 × factorial(3))
= 5 × (4 × (3 × factorial(2)))
= 5 × (4 × (3 × (2 × factorial(1))))
= 5 × (4 × (3 × (2 × 1)))    ← 基线条件触发
= 5 × (4 × (3 × 2))
= 5 × (4 × 6)
= 5 × 24
= 120

可以看到，递归调用是层层嵌套的，每一层都需要等待下一层的结果。

JavaScript 调用栈原理

什么是调用栈（Call Stack）？

JavaScript 引擎（如 V8）使用调用栈来管理函数调用。每当一个函数被调用，一个新的栈帧（Stack Frame）被压入栈顶；函数执行完毕，栈帧弹出。

function a() {
  console.log('a start');
  b();
  console.log('a end');
}

function b() {
  console.log('b start');
  c();
  console.log('b end');
}

function c() {
  console.log('c');
}

a();

调用栈的变化过程：

调用 a() 时：
┌─────────┐  ← 栈顶
│   a()   │
└─────────┘

a() 调用 b() 时：
┌─────────┐  ← 栈顶
│   b()   │
├─────────┤
│   a()   │
└─────────┘

b() 调用 c() 时：
┌─────────┐  ← 栈顶
│   c()   │
├─────────┤
│   b()   │
├─────────┤
│   a()   │
└─────────┘

c() 返回后：
┌─────────┐  ← 栈顶
│   b()   │
├─────────┤
│   a()   │
└─────────┘

栈溢出的原因

当递归层数过深，或者递归没有正确的基线条件时，调用栈会被塞满，JS 引擎抛出 RangeError: Maximum call stack size exceeded。

// ❌ 没有基线条件的递归 —— 立即栈溢出
function infinite() {
  infinite();  // 无限递归
}
infinite();
// RangeError: Maximum call stack size exceeded

// ❌ 基线条件错误 —— 也会栈溢出
function broken(n) {
  if (n === 0) return 0;
  // 错误：n 从未减小，永远不会到达基线
  return broken(n);  // 永远传的是同一个 n
}
broken(5);

JavaScript 的栈大小限制

不同浏览器/引擎的栈大小不同，通常递归深度限制在 10,000 ~ 15,000 层左右：

// 测试最大递归深度
function testDepth(n) {
  try {
    testDepth(n + 1);
  } catch (e) {
    console.log(`最大递归深度约为: ${n}`);
  }
}
testDepth(0);
// 输出：最大递归深度约为: 10000+（具体数值因环境而异）

尾递归（Tail Recursion）

什么是尾递归？

如果一个递归调用是函数体中最后执行的语句，这个递归就是尾递归。

// ❌ 非尾递归：递归调用后还需要做乘法
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);  // 递归后还有乘法操作
}

// ✅ 尾递归：递归调用是最后一步，用 accumulator 累积结果
function factorialTail(n, acc = 1) {
  if (n <= 1) return acc;
  return factorialTail(n - 1, acc * n);  // 递归调用即最后一步
}

尾调用优化（TCO）

理论上，尾递归可以被优化为循环，不需要增加新的栈帧。这就是尾调用优化（Tail Call Optimization）。

非尾递归（需要保存栈帧）：
factorial(5)
→ 5 * factorial(4)   ← 需要记住「乘以 5」
→ 5 * (4 * factorial(3))  ← 需要记住「乘以 4」
→ ... 栈帧一直在增长

尾递归（理论上可优化）：
factorialTail(5, 1)
→ factorialTail(4, 5)
→ factorialTail(3, 20)
→ factorialTail(2, 60)
→ factorialTail(1, 120)
→ 120  ← 直接返回，不需要回溯

ES6 的尾调用优化限制

虽然 ES6 规范允许引擎实现尾调用优化，但大多数现代 JS 引擎并没有实现它（特别是 V8/Chrome）。原因包括：

调试体验变差（栈追踪信息丢失）
优化收益有限
严格模式限制

// 即使在 ES6 严格模式下，V8 也不会做 TCO
'use strict';
function sum(n, acc = 0) {
  if (n <= 0) return acc;
  return sum(n - 1, acc + n);  // 理论上应该被优化
}
// 实际上在 Chrome/V8 中仍然会栈溢出

结论：不能依赖尾调用优化。 需要自己实现迭代改写。

解决方案一：迭代改写

将递归改写为 for 或 while 循环，彻底避免栈溢出。

// 递归版阶乘
function factorialRec(n) {
  if (n <= 1) return 1;
  return n * factorialRec(n - 1);
}

// 迭代版阶乘（推荐）
function factorialIter(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

// 递归版求和
function sumRec(n) {
  if (n <= 0) return 0;
  return n + sumRec(n - 1);
}

// 迭代版求和
function sumIter(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}

斐波那契数列的迭代改写

// ❌ 递归版：O(2^n) 指数级复杂度，n=40 就很慢
function fibRec(n) {
  if (n <= 1) return n;
  return fibRec(n - 1) + fibRec(n - 2);
}

// ✅ 迭代版：O(n) 线性复杂度
function fibIter(n) {
  if (n <= 1) return n;
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];  // 解构赋值交换
  }
  return curr;
}

console.log(fibIter(1000)); // 可以轻松计算很大的 n

解决方案二：记忆化（Memoization）

对于递归中重复计算的问题，记忆化是一种有效的优化手段。

// 有记忆化的斐波那契
function fibMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];  // 查缓存

  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

console.log(fibMemo(100)); // 快速计算，不会栈溢出

通用记忆化工具函数

function memoize(fn) {
  const cache = new Map();
  return function(...args) {
    const key = JSON.stringify(args);
    if (cache.has(key)) {
      return cache.get(key);
    }
    const result = fn.apply(this, args);
    cache.set(key, result);
    return result;
  };
}

// 使用
const fib = memoize(function(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
});

console.log(fib(100)); // 高效

解决方案三：Trampoline（蹦床函数）

蹦床函数是一种将递归「降维」的技术，通过返回函数而不是直接调用来避免栈增长。

// 蹦床函数
function trampoline(fn) {
  return function(...args) {
    let result = fn.apply(this, args);
    while (typeof result === 'function') {
      result = result();  // 不断执行返回的函数
    }
    return result;
  };
}

// 尾递归函数，但返回函数而不是直接递归
function factorialTrampoline(n, acc = 1) {
  if (n <= 1) return acc;
  // 返回一个函数，而不是直接调用自身
  return () => factorialTrampoline(n - 1, acc * n);
}

// 包装使用
const safeFactorial = trampoline(factorialTrampoline);
console.log(safeFactorial(10000)); // 不会栈溢出！

原理：每次递归调用不立即执行，而是返回一个「待执行函数」。外层循环不断执行这些函数，由于不是真正的递归调用，调用栈不会增长。

递归模式改写技巧

自顶向下 vs 自底向上

// 自顶向下（递归，容易栈溢出）
function climbStairsTopDown(n, memo = {}) {
  if (n <= 2) return n;
  if (memo[n]) return memo[n];
  memo[n] = climbStairsTopDown(n - 1, memo) + climbStairsTopDown(n - 2, memo);
  return memo[n];
}

// 自底向上（迭代，推荐）
function climbStairsBottomUp(n) {
  if (n <= 2) return n;
  let prev = 1, curr = 2;
  for (let i = 3; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

使用 reduce 替代递归

// 递归：数组求和
function sumArr(arr, i = 0) {
  if (i >= arr.length) return 0;
  return arr[i] + sumArr(arr, i + 1);
}

// 迭代：reduce（更简洁）
const sumArr2 = arr => arr.reduce((sum, val) => sum + val, 0);

常见递归场景与最优解

场景	递归写法	最优解
阶乘	`n * fact(n-1)`	迭代 for 循环
斐波那契	`fib(n-1) + fib(n-2)`	迭代 + 缓存
数组扁平化	`flat(arr[0]) + flat(arr.slice(1))`	栈/while 循环
深拷贝	`JSON.parse(JSON.stringify())` 或递归	迭代 BFS/DFS
树遍历	递归 DFS	迭代 + 栈

树递归的迭代改写示例

// 递归 DFS 遍历树
function dfsRec(node, result = []) {
  if (!node) return result;
  result.push(node.val);
  for (const child of node.children) {
    dfsRec(child, result);
  }
  return result;
}

// 迭代 DFS 遍历树（用栈模拟）
function dfsIter(root) {
  const result = [];
  const stack = [root];
  while (stack.length > 0) {
    const node = stack.pop();
    if (!node) continue;
    result.push(node.val);
    // 逆序压栈，保证正序遍历
    for (let i = node.children.length - 1; i >= 0; i--) {
      stack.push(node.children[i]);
    }
  }
  return result;
}

总结

栈溢出原因：递归层数过深，调用栈空间耗尽
尾递归：虽然 ES6 规范支持，但 V8 等主流引擎未实现，不能依赖
解决方案优先级：
- 首选：迭代改写（最简单、最可靠）
- 次选：记忆化（减少重复计算，适合分治递归）
- 特殊：蹦床函数（保持递归思维但避免栈溢出）
编写递归时的检查清单：
- ✅ 有正确的基线条件吗？
- ✅ 每次递归参数都在向基线条件靠近吗？
- ✅ 能否改写为迭代？
- ✅ 是否有重复计算可以用记忆化优化？

递归是优雅的，但迭代是可靠的。在生产环境中，优先选择无需担心栈大小的迭代方案。