【8】递归之经典题型总结

📚博客主页：代码探秘者

✨专栏：《JavaSe》 其他更新ing…

❤️感谢大家点赞👍🏻收藏⭐评论✍🏻，您的三连就是我持续更新的动力❤️

🙏作者水平有限，欢迎各位大佬指点，相互学习进步！

---

Java递归全面总结

一、递归基础概念

1. 定义：

   • 方法直接或间接调用自身的过程
   • 必须包含递归条件和基线条件

2. 核心要素：

   • 递归条件（Recursive Case）：方法继续调用自身的条件
   • 基线条件（Base Case）：终止递归的条件

3. 执行原理：

   public void recursiveMethod(int n) {if (n <= 0) {  // 基线条件return;}System.out.println(n);recursiveMethod(n-1);  // 递归条件
   }
   

4. 内存机制：

   • 每次递归调用都会在栈内存中创建新的栈帧
   • 栈深度过大时会导致StackOverflowError（典型深度约5000-7000层）

二、递归注意事项（⚠️重点）

1. 必须要有终止条件：否则无限递归导致栈溢出
2. 递归深度控制：对于大数据量问题，考虑改用循环
3. 重复计算问题：如斐波那契数列的朴素递归效率极低
4. 空间复杂度：递归调用栈会消耗额外内存
5. 尾递归优化：Java不支持自动优化，但可手动实现

三、经典递归问题

1. 阶乘计算

解题思路：

1. 基线条件：1的阶乘是1
2. 递归关系：n! = n × (n-1)!
3. 逐步拆解问题直到达到基线条件

/*** 计算n的阶乘* @param n 要计算阶乘的数字* @return n的阶乘结果*/
public static int factorial(int n) {// 基线条件：1的阶乘为1if (n == 1) return 1;// 递归条件：n! = n * (n-1)!return n * factorial(n - 1);
}
// 示例：factorial(5) → 120

2. 斐波那契数列（优化版）

解题思路：

1. 基线条件：F(0)=0，F(1)=1
2. 递归关系：F(n) = F(n-1) + F(n-2)
3. 使用备忘录避免重复计算

// 备忘录数组
static int[] memo = new int[100];public static int fibonacci(int n) {// 基线条件if (n <= 1) return n;// 检查是否已计算过if (memo[n] != 0) return memo[n];// 递归计算并存储结果memo[n] = fibonacci(n-1) + fibonacci(n-2);return memo[n];
}
// 示例：fibonacci(10) → 55

3. 汉诺塔问题

解题思路：

1. 将n个盘子从A移到C =
   • 先把n-1个从A移到B（借助C）
   • 移动第n个到C
   • 把n-1个从B移到C（借助A）
2. 最小规模问题：1个盘子直接移动

public static void hanoi(int n, char from, char to, char aux) {// 基线条件：只剩一个盘子if (n == 1) {System.out.println("移动盘子 1 从 " + from + " 到 " + to);return;}// 将n-1个盘子移到辅助柱hanoi(n-1, from, aux, to);// 移动最下面的盘子System.out.println("移动盘子 " + n + " 从 " + from + " 到 " + to);// 将n-1个盘子移回目标柱hanoi(n-1, aux, to, from);
}
// 示例：hanoi(3, 'A', 'C', 'B')

4. 二叉树前序遍历

解题思路：

1. 访问根节点
2. 递归遍历左子树
3. 递归遍历右子树
4. 基线条件：节点为null时返回

class TreeNode {int val;TreeNode left;TreeNode right;
}public static void preOrder(TreeNode root) {// 基线条件：空树if (root == null) return;// 1. 访问根节点System.out.print(root.val + " ");// 2. 递归遍历左子树preOrder(root.left);// 3. 递归遍历右子树preOrder(root.right);
}
// 示例输出：根 → 左 → 右

5. 全排列问题

解题思路：

1. 固定第一个位置，递归求后面所有排列
2. 通过交换元素实现不同排列
3. 基线条件：start到达数组末尾

public static void permute(int[] nums, int start) {// 基线条件：已处理完所有元素if (start == nums.length - 1) {System.out.println(Arrays.toString(nums));return;}for (int i = start; i < nums.length; i++) {// 交换元素到当前位置swap(nums, start, i);// 递归生成后续排列permute(nums, start + 1);// 恢复原始顺序（回溯）swap(nums, start, i);}
}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}
// 示例：permute([1,2,3], 0)

6. 快速排序（分治递归）

解题思路：

1. 选择基准元素（pivot）
2. 将数组分为小于和大于基准的两部分
3. 递归排序两个子数组
4. 基线条件：数组长度<=1

public static void quickSort(int[] arr, int low, int high) {// 基线条件：子数组长度为0或1if (low < high) {// 获取分区点int pi = partition(arr, low, high);// 递归排序左半部分quickSort(arr, low, pi - 1);// 递归排序右半部分quickSort(arr, pi + 1, high);}
}private static int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;swap(arr, i, j);}}swap(arr, i + 1, high);return i + 1;
}
// 示例：quickSort(arr, 0, arr.length-1)

7. 反转字符串

解题思路：

1. 基线条件：空字符串或单字符
2. 递归关系：reverse(s) = reverse(s.substring(1)) + s.charAt(0)
3. 逐步将首字符移到末尾

public static String reverse(String s) {// 基线条件：空串或单字符if (s.isEmpty()) return s;// 递归反转：首字符放到最后return reverse(s.substring(1)) + s.charAt(0);
}
// 示例：reverse("hello") → "olleh"

8. 最大公约数（欧几里得算法）

解题思路：

1. 基线条件：b为0时返回a
2. 递归关系：gcd(a,b) = gcd(b, a%b)
3. 基于数学定理的优雅解法

public static int gcd(int a, int b) {// 基线条件：余数为0if (b == 0) return a;// 递归计算gcd(b, a mod b)return gcd(b, a % b);
}
// 示例：gcd(48, 18) → 6

四、递归问题解决通用模板：

1. 定义基线条件：最简单情况直接返回结果
2. 分解问题：将大问题拆解为相似小问题
3. 递归调用：用更小规模参数调用自身
4. 合并结果：将小问题的解组合成大问题的解

复杂度对比表：

问题	时间复杂度	空间复杂度	优化方法
阶乘	O(n)	O(n)	尾递归改写
斐波那契	O(2^n)→O(n)	O(n)	备忘录/动态规划
汉诺塔	O(2^n)	O(n)	无（问题本质决定）
二叉树遍历	O(n)	O(h)	莫里斯遍历
全排列	O(n!)	O(n)	堆算法

注：实际开发中应优先考虑迭代解法，递归更适合表达清晰的算法逻辑。对于深度可能超过1000层的问题，建议使用栈模拟递归或改用动态规划。

五、递归优化技巧

1. 备忘录法（记忆化搜索）：

   // 斐波那契优化示例
   static int[] memo = new int[100];
   public static int fib(int n) {if (n <= 1) return n;if (memo[n] != 0) return memo[n];memo[n] = fib(n-1) + fib(n-2);return memo[n];
   }
   

2. 尾递归改写：

   // 阶乘的尾递归版本
   public static int factorialTail(int n, int accumulator) {if (n == 1) return accumulator;return factorialTail(n-1, n * accumulator);
   }
   

3. 改迭代实现：

   // 斐波那契迭代版
   

六、递归应用场景

1. 树形结构操作：二叉树遍历、文件系统遍历
2. 分治算法：归并排序、快速排序
3. 回溯算法：八皇后问题、数独求解
4. 动态规划：背包问题（记忆化搜索实现）
5. 数学问题：组合计算、泰勒展开

七、递归思维训练建议

1. 从简单案例入手（如阶乘、斐波那契）
2. 画递归调用树理解执行流程
3. 使用IDE调试功能观察调用栈变化
4. 先写基线条件，再写递归条件
5. 注意参数在递归过程中的变化规律