加载中…
应用场景：树遍历 · 分治 · 回溯
交互式动画演示，可调整参数并单步执行。
全屏打开递归（Recursion） 是一种解决问题的方法，其中函数调用自身来解决问题的小实例。
graph TD F[factorial n] --> G[return 1] F -. n > 1 .-> R[n * factorial n-1] R --> Next[factorial n-1] Next --> G2[Base Case] G2[Base Case] -.-> R
递归 = 自己调用自己，必须有 base case。
public class Factorial {
public static int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
}
return n * factorial(n - 1);
}
public static int factorialIterative(int n) {
int result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
}递归函数调用会形成调用栈：
factorial(4)
= 4 * factorial(3)
= 4 * 3 * factorial(2)
= 4 * 3 * 2 * factorial(1)
= 4 * 3 * 2 * 1
= 24
public class Hanoi {
public static void hanoi(int n, char from, char to, char aux) {
if (n == 1) {
System.out.println("Move disk 1 from " + from + " to " + to);
return;
}
hanoi(n - 1, from, aux, to);
System.out.println("Move disk " + n + " from " + from + " to " + to);
hanoi(n - 1, aux, to, from);
}
}public static int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}| 特点 | 递归 | 迭代 |
|---|---|---|
| 代码简洁性 | ✅ 更简洁 | 需要循环 |
| 空间复杂度 | O(n) 调用栈 | O(1) |
| 时间复杂度 | 可能较高 | 通常较低 |
| 思维难度 | 容易理解 | 需要构造循环 |
对于斐波那契数列，可以使用记忆化避免重复计算：
public static int fibonacciMemo(int n, Map<Integer, Integer> memo) {
if (n <= 1) return n;
if (memo.containsKey(n)) return memo.get(n);
int result = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
memo.put(n, result);
return result;
}用递归树直观理解递归的时间复杂度：
fib(n) 的递归树（未记忆化）：
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) ... ...
问题：fib(3) 被计算了 2 次，fib(2) 被计算了 3 次！
节点总数 ≈ 2^n → 指数复杂度 O(2^n)
加上记忆化后：每个 fib(i) 只算一次 → O(n)
递归复杂度分析三步法：
归并排序：T(n) = 2T(n/2) + O(n) → O(n log n)
二分查找：T(n) = T(n/2) + O(1) → O(log n)
冒泡递归：T(n) = T(n-1) + O(n) → O(n²)
| 题目 | 难度 | 核心思路 |
|---|---|---|
| 反转链表（LC 206） | 🟢 Easy | 递归反转：假设后面已反转，处理当前节点 |
| 汉诺塔（经典） | 🟡 Medium | n-1 个移开 → 移最大的 → n-1 个移回 |
| 全排列（LC 46） | 🟡 Medium | 递归 + 回溯 |
| 子集（LC 78） | 🟡 Medium | 每个元素选/不选 |
| 实现 pow(x,n)（LC 50） | 🟡 Medium | 快速幂：x^n = (x^{n/2})² |
| 第 N 个泰波那契数（LC 1137） | 🟢 Easy | 记忆化递归 or 迭代 |
1. 忘记基准条件 → 栈溢出
// ❌ 没有终止条件，无限递归直到 StackOverflowError
int sum(int n) { return n + sum(n - 1); }
// ✅ 必须有基准条件
int sum(int n) { return n <= 0 ? 0 : n + sum(n - 1); }
2. 递归深度超限
Python 默认递归深度限制 1000，Java 栈默认约 10⁴ 层。n = 10⁵ 的链状递归必须改写为迭代或显式栈。
3. 重复子问题未记忆化
# ❌ fib(40) 就要算上亿次
# ✅ 加 lru_cache 或手写 memo
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n): return n if n < 2 else fib(n-1) + fib(n-2)
4. 递归中修改外部状态的顺序
回溯算法中，“做选择 → 递归 → 撤销选择”的顺序不能乱，撤销必须在递归返回后立即执行。
练习推荐：先手写 [反转链表（LC 206）] 的递归版，理解“假设子问题已解决”的思维。