递归详解与应用
概述
递归 是一种编程技巧，函数调用自身来解决问题。递归的核心思想是：将大问题分解为相同的小问题，直到问题足够小可以直接求解。
💡 提示: 核心思想
递归 = 自我调用 + 终止条件 + 问题分解
一、递归的三个要素
1.1 递归的本质
递归就是函数调用自己，但每次调用都在处理一个更小的问题。
1
2
3
4
5
6
7
8
9
10
11
| 大问题
↓
分解为更小的问题 + 调用自己
↓
继续分解
↓
直到问题足够小
↓
直接求解（返回结果）
↓
逐层返回结果
|
1.2 递归的三个必要条件
| 条件 |
说明 |
重要性 |
| 递归关系 |
函数调用自身 |
必须 |
| 终止条件 |
何时停止递归 |
必须（没有会无限循环） |
| 问题分解 |
如何将大问题分解为小问题 |
必须 |
1.3 递归的通用模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
返回值类型 recursiveFunction(参数) {
if (终止条件) {
return 基础情况的结果;
}
返回值 = recursiveFunction(更小的参数);
return 处理后的结果;
}
|
二、递归的执行过程
2.1 递归栈的概念
当函数调用自己时，每次调用都会在栈上创建一个新的函数执行环境。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 递归调用过程：
recursion(5)
↓ 调用
recursion(4)
↓ 调用
recursion(3)
↓ 调用
recursion(2)
↓ 调用
recursion(1)
↓ 到达终止条件
return 1
↑ 返回
return 2 * 1 = 2
↑ 返回
return 3 * 2 = 6
↑ 返回
return 4 * 6 = 24
↑ 返回
return 5 * 24 = 120
|
2.2 递归栈的内存占用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 栈内存：
┌─────────────────┐
│ recursion(1) │ ← 最后入栈
│ 局部变量: n=1 │
├─────────────────┤
│ recursion(2) │
│ 局部变量: n=2 │
├─────────────────┤
│ recursion(3) │
│ 局部变量: n=3 │
├─────────────────┤
│ recursion(4) │
│ 局部变量: n=4 │
├─────────────────┤
│ recursion(5) │ ← 最先入栈
│ 局部变量: n=5 │
└─────────────────┘
递归深度 = 5
栈空间 = 5 × 每个函数的空间
|
关键点：
- 每次递归调用都会占用栈空间
- 递归深度越深，占用的栈空间越多
- 栈空间有限，过深的递归会导致栈溢出
三、递归的实际例子
3.1 例子1：计算阶乘
问题分析
1
2
3
4
5
| 5! = 5 × 4!
4! = 4 × 3!
3! = 3 × 2!
2! = 2 × 1!
1! = 1（基础情况）
|
递归关系：n! = n × (n-1)!
终止条件：n == 1
递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
int factorial(int n) {
if (n == 1) {
return 1;
}
int result = n * factorial(n - 1);
return result;
}
int result = factorial(5);
|
执行过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| factorial(5)
↓ 5 != 1，继续递归
↓ 计算 5 * factorial(4)
↓ factorial(4)
↓ 4 != 1，继续递归
↓ 计算 4 * factorial(3)
↓ factorial(3)
↓ 3 != 1，继续递归
↓ 计算 3 * factorial(2)
↓ factorial(2)
↓ 2 != 1，继续递归
↓ 计算 2 * factorial(1)
↓ factorial(1)
↓ 1 == 1，到达终止条件
↓ return 1
↓ return 2 * 1 = 2
↓ return 3 * 2 = 6
↓ return 4 * 6 = 24
↓ return 5 * 24 = 120
|
时间复杂度：O(n)
空间复杂度：O(n)（递归栈深度）
3.2 例子2：链表遍历（树遍历的基础）
问题分析
1
2
3
4
5
6
| 链表：1 → 2 → 3 → null
遍历思路：
- 访问当前节点
- 递归遍历下一个节点
- 终止条件：节点为 null
|
递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
void traverse(ListNode node) {
if (node == null) {
return;
}
System.out.println(node.val);
traverse(node.next);
}
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
traverse(head);
|
执行过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| traverse(node1)
↓ node1 != null
↓ 打印 1
↓ 调用 traverse(node2)
↓ traverse(node2)
↓ node2 != null
↓ 打印 2
↓ 调用 traverse(node3)
↓ traverse(node3)
↓ node3 != null
↓ 打印 3
↓ 调用 traverse(null)
↓ traverse(null)
↓ null == null，到达终止条件
↓ return
↓ return
↓ return
↓ return
|
关键点：
- 每次递归都处理一个节点
- 通过
node.next 将问题分解为更小的问题
- 当
node == null 时停止递归
3.3 例子3：二叉树前序遍历
问题分析
1
2
3
4
5
6
7
8
9
10
11
12
| 树结构：
1
/ \
2 3
前序遍历：根 → 左子树 → 右子树
输出：1 2 3
递归思路：
1. 访问根节点
2. 递归遍历左子树
3. 递归遍历右子树
|
递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
void preorder(TreeNode node) {
if (node == null) {
return;
}
System.out.println(node.val);
preorder(node.left);
preorder(node.right);
}
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
preorder(root);
|
执行过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| preorder(node1)
↓ node1 != null
↓ 打印 1
↓ 调用 preorder(node2)
↓ preorder(node2)
↓ node2 != null
↓ 打印 2
↓ 调用 preorder(null)
↓ return
↓ 调用 preorder(null)
↓ return
↓ return
↓ 调用 preorder(node3)
↓ preorder(node3)
↓ node3 != null
↓ 打印 3
↓ 调用 preorder(null)
↓ return
↓ 调用 preorder(null)
↓ return
↓ return
↓ return
|
关键点：
- 递归处理三个部分：根、左子树、右子树
- 每个递归调用都是独立的，处理一个子树
- 通过
node == null 判断是否继续递归
四、递归的三个关键概念
4.1 递归的”信任”
关键思想：不要试图追踪整个递归过程，而是相信递归函数能正确处理更小的问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
void preorder(TreeNode node) {
if (node == null) return;
System.out.println(node.val);
preorder(node.left);
preorder(node.right);
}
void preorder(TreeNode node) {
if (node == null) return;
System.out.println(node.val);
preorder(node.left);
preorder(node.right);
}
|
关键：
- 不要试图在脑子里模拟整个递归过程
- 只需要确保：终止条件正确 + 递归关系正确
- 相信递归函数能处理更小的问题
4.2 递归的”分治”
分治思想：将大问题分解为相同的小问题。
1
2
3
4
5
6
7
8
| 大问题：遍历整个树
↓ 分解
小问题1：处理根节点
小问题2：遍历左子树（与大问题相同，但规模更小）
小问题3：遍历右子树（与大问题相同，但规模更小）
↓ 递归处理小问题
↓ 合并结果
完成
|
关键：
- 每次递归都在处理一个更小的问题
- 问题的结构相同，只是规模不同
- 最终会到达基础情况（终止条件）
4.3 递归的”回溯”
回溯思想：递归会自动回溯，逐层返回结果。
1
2
3
4
5
| 递归下降：
level 1 → level 2 → level 3 → ... → 基础情况
↓
回溯上升：
level 1 ← level 2 ← level 3 ← ... ← 返回结果
|
1
2
3
4
5
6
7
8
9
10
11
12
|
void postorder(TreeNode node) {
if (node == null) return;
postorder(node.left);
postorder(node.right);
System.out.println(node.val);
}
|
五、递归 vs 迭代
5.1 对比表
| 维度 |
递归 |
迭代 |
| 代码简洁性 |
简洁、易读 |
复杂、需要手动管理状态 |
| 空间复杂度 |
O(h)（递归栈） |
O(1)（通常） |
| 时间复杂度 |
相同 |
相同 |
| 栈溢出风险 |
高（深度大时） |
无 |
| 理解难度 |
需要理解递归思想 |
相对直观 |
| 性能 |
略低（函数调用开销） |
略高 |
5.2 递归 vs 迭代：链表遍历
递归方式
1
2
3
4
5
6
7
8
| void traverse(ListNode node) {
if (node == null) return;
System.out.println(node.val);
traverse(node.next);
}
|
迭代方式
1
2
3
4
5
6
7
8
9
10
| void traverse(ListNode node) {
ListNode current = node;
while (current != null) {
System.out.println(current.val);
current = current.next;
}
}
|
5.3 递归 vs 迭代：树遍历
递归方式（前序）
1
2
3
4
5
6
7
8
| void preorder(TreeNode node) {
if (node == null) return;
System.out.println(node.val);
preorder(node.left);
preorder(node.right);
}
|
迭代方式（前序）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void preorderIterative(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.println(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
|
关键观察：
- 递归本质上是利用系统栈
- 迭代是手动管理栈
- 递归简洁，迭代高效
六、递归的常见陷阱
6.1 陷阱1：没有终止条件
1
2
3
4
5
6
7
8
9
10
11
12
|
void recursion(int n) {
System.out.println(n);
recursion(n + 1);
}
void recursion(int n) {
if (n > 10) return;
System.out.println(n);
recursion(n + 1);
}
|
6.2 陷阱2：终止条件永远不会到达
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void recursion(int n) {
if (n == 0) return;
System.out.println(n);
recursion(n - 2);
}
void recursion(int n) {
if (n <= 0) return;
System.out.println(n);
recursion(n - 2);
}
|
6.3 陷阱3：问题没有真正分解
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void recursion(int n) {
if (n == 0) return;
System.out.println(n);
recursion(n);
}
void recursion(int n) {
if (n == 0) return;
System.out.println(n);
recursion(n - 1);
}
|
6.4 陷阱4：栈溢出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
void recursion(int n) {
if (n == 0) return;
recursion(n - 1);
}
recursion(100000);
for (int i = 100000; i > 0; i--) {
}
|
七、递归的应用场景
7.1 适合用递归的场景
| 场景 |
原因 |
例子 |
| 树/图遍历 |
天然的递归结构 |
前序、中序、后序遍历 |
| 分治算法 |
问题可分解 |
快速排序、归并排序 |
| 回溯算法 |
需要尝试所有可能 |
N 皇后、组合问题 |
| 动态规划 |
有重叠子问题 |
斐波那契数列 |
7.2 不适合用递归的场景
| 场景 |
原因 |
替代方案 |
| 线性遍历 |
迭代更高效 |
使用 while 循环 |
| 深度很大 |
容易栈溢出 |
使用迭代或增加栈大小 |
| 性能关键 |
函数调用开销大 |
使用迭代 |
八、递归的调试技巧
8.1 打印递归栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void preorder(TreeNode node, int depth) {
if (node == null) return;
String indent = " ".repeat(depth);
System.out.println(indent + "进入: " + node.val);
preorder(node.left, depth + 1);
preorder(node.right, depth + 1);
System.out.println(indent + "返回: " + node.val);
}
|
8.2 验证终止条件
1
2
3
4
5
6
7
8
9
10
11
| void recursion(int n) {
System.out.println("递归调用: n = " + n);
if (n == 0) {
System.out.println("到达终止条件");
return;
}
recursion(n - 1);
}
|
8.3 检查问题分解
1
2
3
4
5
6
7
8
9
10
11
| void recursion(int n) {
System.out.println("处理问题大小: " + n);
if (n <= 1) return;
int nextSize = n - 1;
System.out.println("下一个问题大小: " + nextSize);
recursion(nextSize);
}
|
九、递归思维的培养
9.1 三步法
第1步：明确递归的三个要素
- 终止条件是什么？
- 递归关系是什么？
- 如何分解问题？
第2步：相信递归
- 不要试图追踪整个过程
- 只需确保逻辑正确
- 相信递归能处理更小的问题
第3步：验证
- 测试基础情况
- 测试简单情况（n=1, 2, 3）
- 测试复杂情况
9.2 练习建议
1
2
3
4
5
6
7
8
|
1. 阶乘：factorial(n)
2. 斐波那契：fib(n)
3. 链表遍历：traverse(node)
4. 树遍历：preorder(node)
5. 二分查找：binarySearch(arr, target)
6. 快速排序：quickSort(arr)
7. 回溯：permutation(arr)
|
相关笔记