【JavaScript】递归的问题以及优化方法

1. 递归多会导致内存消耗变大

• 递归的本质：函数调用自己，每次调用会在 调用栈 上压入一帧（栈帧），里面保存：

  • 局部变量
  • 参数
  • 返回地址
  • 执行上下文

• 当递归层级很多时：

  • 调用栈帧越来越多 → 内存消耗增加
  • 如果层级过深 → 触发 栈溢出（Stack Overflow）

👉 举例：

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}
factorial(100000); // 🔥 Maximum call stack size exceeded

这里就是因为递归深度太大，每一层都占内存，最后栈爆了。

2. 怎么优化递归？

（1）尾递归优化（Tail Recursion）

• 原理：如果递归调用是函数的最后一步，可以不需要保留当前栈帧，直接复用（更新参数，而不是创建新的栈帧） → 内存消耗低。
• ES6 有尾调用优化的提案，但目前大部分 JS 引擎 没实现（在某些语言如 Scala、Haskell 是默认优化）。

// 普通递归
function sum(n) {
  if (n === 1) return 1;
  return n + sum(n - 1);
}

// 尾递归
function sumTail(n, acc = 0) {
  if (n === 0) return acc;
  return sumTail(n - 1, acc + n); // ✅ 最后一步是递归调用
}

sumTail(100000, 0); // 理论上不会栈溢出

（2）递归改迭代

• 思路：用循环 + 栈/队列模拟递归，避免调用栈过深。

// 递归版
function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

// 迭代版
function factorialIter(n) {
  let res = 1;
  for (let i = 1; i <= n; i++) {
    res *= i;
  }
  return res;
}

👉 迭代的空间复杂度通常是 O(1)，比递归更省内存。

（3）分治 + 记忆化（减少重复递归）

• 比如 斐波那契数列，递归会大量重复计算，可以用缓存减少递归次数。

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

3. 面试总结答法

递归会导致内存消耗变大，是因为每次函数调用都会在调用栈里保存上下文，如果递归层级太深，栈就会溢出。优化方法包括：

• 使用 尾递归优化（如果语言/引擎支持）。
• 将递归改写为 迭代，降低空间复杂度。
• 使用 记忆化缓存，减少重复递归。