递归（Recursion）
递归是一种通过函数调用自身来解决问题的方法，理解递归最有效的方法是从「树」的角度去抽象和分析。
定义
递归（Recursion）是指一个函数直接或间接调用自身来解决问题的编程技巧。递归算法本质上是一种穷举手段，通过把问题分解成更小的子问题来解决复杂问题。
核心观点：理解和编写递归算法最有效的方法是从「树」的视角去理解，而非从栈、镜像等其他角度。
核心特性
| 特性 | 说明 |
|---|---|
| 自引用 | 函数直接或间接调用自身 |
| 终止条件 | 必须有 base case 防止无限递归 |
| 问题分解 | 将大问题分解为相似的子问题 |
| 树形结构 | 递归调用可以抽象为一棵递归树 |
两种思维模式
编写递归算法只有两种思维模式，都尝试套用一下，必然有一种能写出来：
1. 分解问题（Divide & Conquer）
特点：
- 递归函数有清晰的定义和返回值
- 通过子问题的解推导原问题的解
- 类似数学归纳法的思想
适用场景：斐波那契数列、二叉树最大深度、动态规划问题
代码示例（斐波那契数列）：
// 定义：输入一个非负整数 n，返回斐波那契数列中的第 n 个数
int fib(int n) {
if (n < 2) {
return n;
}
// 利用定义，计算子问题
int fib_n_1 = fib(n - 1);
int fib_n_2 = fib(n - 2);
// 通过子问题的解，计算原问题的解
return fib_n_1 + fib_n_2;
}
可视化理解：
- 递归树上的每个节点就是一个子问题的解
- 父节点等待子节点计算完成，然后合并结果
2. 遍历（Traverse）
特点：
- 递归函数无返回值，单纯遍历
- 通过外部变量（如全局变量）收集结果
- 类似 for 循环的递归版本
适用场景：全排列、组合问题、回溯算法、DFS
代码示例（全排列）：
List<List<Integer>> res = new LinkedList<>();
List<Integer> track = new LinkedList<>();
void backtrack(int[] nums, List<Integer> track) {
if (track.size() == nums.length) {
// 到达叶子节点，收集结果
res.add(new LinkedList<>(track));
return;
}
for (int i = 0; i < nums.length; i++) {
// 做选择
track.add(nums[i]);
backtrack(nums, track);
// 撤销选择
track.removeLast();
}
}
可视化理解：
- 递归树上的节点记录之前的选择
- 所有合法结果都在叶子节点上
从树的角度理解递归
为什么是树？
任何递归算法都可以抽象成一棵树结构：
- 斐波那契数列 → 二叉树（每个节点有两个子节点：fib(n-1) 和 fib(n-2)）
- 全排列 → 多叉树（每个节点有多个子节点，对应每个可选元素）
- 二叉树遍历 → 本身就是树结构
经典递归算法
| 算法 | 思维模式 | 说明 |
|---|---|---|
| 斐波那契数列 | 分解问题 | fib(n) = fib(n-1) + fib(n-2) |
| 二叉树最大深度 | 分解问题 / 遍历 | 两种思路都可以解决 |
| 全排列 | 遍历 | 回溯法收集所有叶子节点 |
| 归并排序 | 分解问题 | 后序遍历：先排左右，再合并 |
| 快速排序 | 分解问题 | 前序遍历：先排好一个元素，再排左右 |
| 二叉树遍历 | 遍历 | 前序/中序/后序位置的应用 |
与类似概念对比
| 维度 | 递归 | 迭代 |
|---|---|---|
| 实现方式 | 函数调用自身 | 循环结构 |
| 本质 | 穷举（遍历递归树） | 穷举（按规则迭代） |
| 空间开销 | 递归栈 O(深度) | 通常 O(1) |
| 可读性 | 通常更简洁 | 可能更复杂 |
| 适用场景 | 树形问题、分治问题 | 线性问题、状态简单问题 |
| 维度 | 分解问题思维 | 遍历思维 |
|---|---|---|
| 函数返回值 | 有，返回子问题解 | 无，用外部变量收集 |
| 类似模式 | 动态规划、分治 | 回溯、DFS |
| 理解方式 | 数学归纳法 | 遍历/循环 |
注意事项
- 必须有 base case：否则会无限递归导致栈溢出
- 避免重复计算：如斐波那契递归有大量重复子问题，可用记忆化优化
- 递归深度限制：过深的递归可能导致栈溢出，可考虑改为迭代
- 副作用：遍历思维中用外部变量可能产生副作用，需注意状态管理
应用场景
相关概念
- 二叉树：递归算法最天然的应用场景
- DFS：深度优先搜索本质是递归遍历
- 动态规划：分解问题思维的延伸，加入记忆化
- 分治算法：分解问题思维的典型应用
- 回溯算法：遍历思维的典型应用
- 前序遍历：快速排序的思维模式
- 后序遍历：归并排序的思维模式
参考资料
- 理解递归框架：本文的原始资料摘要
- 二叉树系列算法核心纲领：递归在二叉树中的应用
- 归并排序-总结：分解问题思维的实例
- 快速排序算法：分解问题思维的实例
- 动态规划框架：用递归作为基础讲解动态规划，展示递归到DP的演进