文章目录
理解递归可以是一个挑战,但通过一些系统的方法,你可以逐步掌握它。以下是一些帮助你理解递归的策略和步骤:
1. 理解递归的基本概念
递归的基本思想是一个函数调用自身来解决一个更小的相同问题,直到达到基准情况(递归出口),在这个情况下不再进行递归调用。
2. 识别递归的三个关键部分
- 基准情况(Base Case):递归什么时候停止。
- 递归步骤(Recursive Step):函数如何分解问题并递归调用自身。
- 组合结果(Combining Results):如何组合递归调用的结果来解决原问题。
3. 逐步分析递归函数
通过逐步分析每个递归调用,你可以更好地理解递归的执行流程。让我们用一个经典的例子:计算阶乘。
public int factorial(int n) {
if (n == 0) { // 基准情况
return 1;
} else {
return n * factorial(n - 1); // 递归步骤
}
}
分析
- 基准情况:
n == 0
时返回 1。 - 递归步骤:
n * factorial(n - 1)
。 - 组合结果:每次递归调用结果与当前
n
相乘。
4. 手动模拟递归调用
用纸和笔手动模拟递归调用的过程。假设 n = 3
,来看 factorial(3)
的调用过程:
factorial(3)
3 * factorial(2)
2 * factorial(1)
1 * factorial(0)
- 返回 1
- 返回
1 * 1 = 1
- 返回
2 * 1 = 2
- 返回
3 * 2 = 6
最终结果是 6。
5. 可视化递归
使用递归树来可视化递归调用。每个节点表示一次递归调用。对于 factorial(3)
,递归树如下:
factorial(3)
|
3 * factorial(2)
|
2 * factorial(1)
|
1 * factorial(0)
|
1
6. 调试和打印
在递归函数中添加打印语句,跟踪每次递归调用的输入和输出。例如:
public int factorial(int n) {
System.out.println("Entering factorial with n = " + n);
if (n == 0) {
System.out.println("Base case reached with n = " + n);
return 1;
} else {
int result = n * factorial(n - 1);
System.out.println("Returning " + result + " for factorial of " + n);
return result;
}
}
7. 从简单的递归问题开始
从简单的问题开始,比如计算阶乘、斐波那契数列、字符串反转,然后逐步解决复杂的问题,如二叉树遍历、动态规划问题。
8. 理解递归与迭代的关系
理解如何将递归转换为迭代(或相反)有助于理解递归。通过将递归函数转换为迭代版本,你可以更好地理解递归的本质。
9. 练习
通过反复练习各种递归问题,加深对递归的理解。比如二叉树遍历、汉诺塔问题、八皇后问题等。
示例 1:递归实现二叉树的后序遍历
以下是二叉树的后序遍历的递归实现,通过逐步解释每次递归调用,帮助理解递归过程:
private void postOrder2(Node node, List<T> list){
if (node == null){
return; // 基准情况
}
postOrder2(node.left, list); // 遍历左子树
postOrder2(node.right, list); // 遍历右子树
list.add(node.value); // 处理当前节点
}
public List<T> postOrder2(){
LinkedList<T> list = new LinkedList<>();
postOrder2(root, list); // 从根节点开始递归
return list; // 返回结果列表
}
分析
对于一个二叉树:
A
/ \
B C
/ \ \
D E F
递归调用过程:
postOrder2(A, list)
postOrder2(B, list)
postOrder2(D, list)
-> 基准情况,返回。postOrder2(E, list)
-> 基准情况,返回。- 处理
B
,添加B
的值。 postOrder2(C, list)
postOrder2(F, list)
-> 基准情况,返回。- 处理
C
,添加C
的值。 - 处理
A
,添加A
的值。
最终结果是 [D, E, B, F, C, A]
。
通过这些方法和练习,你可以逐步掌握递归的概念和应用。
当然,这里有一些经典的递归示例,这些例子将帮助你加深对递归的理解:
示例 2:斐波那契数列
斐波那契数列是一个著名的递归问题,其中每个数是前两个数之和。数列的前两项通常定义为 0 和 1。
public int fibonacci(int n) {
if (n <= 1) { // 基准情况
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2); // 递归步骤
}
分析
对于 fibonacci(4)
:
fibonacci(4)
fibonacci(3) + fibonacci(2)
(fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))
((fibonacci(1) + fibonacci(0)) + 1) + (1 + 0)
((1 + 0) + 1) + 1
- 最终结果为 3。
示例 3:字符串反转
反转一个字符串可以通过递归实现。
public String reverse(String str) {
if (str.isEmpty()) { // 基准情况
return str;
}
return reverse(str.substring(1)) + str.charAt(0); // 递归步骤
}
分析
对于 reverse("abc")
:
reverse("abc")
reverse("bc") + "a"
(reverse("c") + "b") + "a"
(reverse("") + "c") + "b" + "a"
("c") + "b" + "a"
- 最终结果为 “cba”。
示例 4:汉诺塔问题
汉诺塔问题是一种经典的递归问题,要求将 n 个盘子从源柱移动到目标柱,辅助柱作为中间步骤。
public 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);
}
分析
对于 hanoi(2, 'A', 'C', 'B')
:
hanoi(2, 'A', 'C', 'B')
hanoi(1, 'A', 'B', 'C')
Move disk 1 from A to B
Move disk 2 from A to C
hanoi(1, 'B', 'C', 'A')
Move disk 1 from B to C
- 最终结果为:
Move disk 1 from A to B Move disk 2 from A to C Move disk 1 from B to C
示例 5:二叉树的最大深度
计算二叉树的最大深度(或高度)。
public int maxDepth(TreeNode root) {
if (root == null) { // 基准情况
return 0;
}
int leftDepth = maxDepth(root.left); // 递归步骤
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1; // 组合结果
}
分析
对于以下二叉树:
1
/ \
2 3
/ \
4 5
maxDepth(root)
maxDepth(2)
,maxDepth(3)
maxDepth(4)
,maxDepth(5)
,0
0
,0
1
,1
2
,1
3
最终结果为 3。
示例 6:全排列
生成一个集合的所有排列。
public void permute(List<Integer> nums, int start, List<List<Integer>> result) {
if (start == nums.size() - 1) { // 基准情况
result.add(new ArrayList<>(nums));
return;
}
for (int i = start; i < nums.size(); i++) {
Collections.swap(nums, start, i);
permute(nums, start + 1, result); // 递归步骤
Collections.swap(nums, start, i);
}
}
public List<List<Integer>> permute(List<Integer> nums) {
List<List<Integer>> result = new ArrayList<>();
permute(nums, 0, result);
return result;
}
分析
对于 permute([1, 2, 3])
:
- 初始调用
permute([1, 2, 3], 0, result)
swap(0, 0) -> permute([1, 2, 3], 1, result)
swap(1, 1) -> permute([1, 2, 3], 2, result)
- 基准情况,添加
[1, 2, 3]
- 基准情况,添加
swap(1, 2) -> permute([1, 3, 2], 2, result)
- 基准情况,添加
[1, 3, 2]
- 基准情况,添加
swap(0, 1) -> permute([2, 1, 3], 1, result)
swap(1, 1) -> permute([2, 1, 3], 2, result)
- 基准情况,添加
[2, 1, 3]
- 基准情况,添加
swap(1, 2) -> permute([2, 3, 1], 2, result)
- 基准情况,添加
[2, 3, 1]
- 基准情况,添加
swap(0, 2) -> permute([3, 2, 1], 1, result)
swap(1, 1) -> permute([3, 2, 1], 2, result)
- 基准情况,添加
[3, 2, 1]
- 基准情况,添加
swap(1, 2) -> permute([3, 1, 2], 2, result)
- 基准情况,添加
[3, 1, 2]
- 基准情况,添加
最终结果为所有排列:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]
通过这些示例,你可以看到递归在解决不同类型问题时的广泛应用。关键在于理解递归的三个部分,并通过模拟、调试和练习来逐步掌握递归的思维方式。
标签:return,递归,示例,factorial,result,深度,permute From: https://blog.csdn.net/m0_49013185/article/details/140540149