递归

🔄 递归调用栈

递归不神秘，本质就是函数调用自身 + 调用栈管理。

🔄递归调用栈

阶乘 n!斐波那契求和 1+2+...+n

n! = n × (n-1)!基线: 0! = 1, 1! = 1

n =5

速度:

🔄 重置

📚 调用栈 (Call Stack)深度: 1

栈为空

栈底 (main)

📝 执行日志步骤: 0 / 0

▶️ 播放

---

🎯 递归三要素

1. 基线条件 (Base Case)

递归的出口，没有它就会无限循环。

if (n <= 1) return 1; // 阶乘: 0! = 1, 1! = 1
if (n <= 1) return n; // 斐波那契: F(0) = 0, F(1) = 1

2. 递归条件 (Recursive Case)

问题分解，把大问题拆成小问题。

return n * factorial(n - 1); // 阶乘
return fib(n - 1) + fib(n - 2); // 斐波那契

3. 问题规模缩小

每次调用，问题规模必须向基线条件靠近。

factorial(5) → factorial(4) → ... → factorial(1) // ✅ 规模减小
factorial(5) → factorial(6) → ...               // ❌ 无限循环

---

📚 调用栈原理

每次函数调用都会在调用栈中创建一个栈帧 (Stack Frame)：

调用: factorial(3)
│
├─ 栈帧: factorial(3), 等待 factorial(2) 返回
│  │
│  ├─ 栈帧: factorial(2), 等待 factorial(1) 返回
│  │  │
│  │  └─ 栈帧: factorial(1), 返回 1 ← 基线条件
│  │
│  └─ 返回 2 * 1 = 2
│
└─ 返回 3 * 2 = 6

空间复杂度 = 最大递归深度 = O(n)

---

⚠️ 递归陷阱

1. 栈溢出 (Stack Overflow)

// 危险！没有基线条件
function infinite() {
  return infinite(); // 💥 栈溢出
}

2. 重复计算 (斐波那契)

fib(5)
├─ fib(4)
│  ├─ fib(3) ← 重复计算
│  └─ fib(2) ← 重复计算
└─ fib(3)    ← 重复计算
   ├─ fib(2)
   └─ fib(1)

解决方案: 记忆化 (Memoization) 或动态规划

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

---

🔄 递归 vs 迭代

特性	递归	迭代
代码简洁度	✅ 更简洁	较长
性能	有调用开销	✅ 更快
内存	O(n) 栈空间	✅ O(1)
调试难度	较难	✅ 较易

原则: 能用迭代就用迭代，递归更适合树、图等天然递归的数据结构。

---

🔗 相关知识

• 栈与队列 - 调用栈的本质
• 二叉树 - 递归的经典应用
• 动态规划 - 递归的优化