理解递归框架
raw/articles/2026/05/理解递归框架.md
一句话总结
从「树」的角度理解递归，掌握「遍历」和「分解问题」两种递归思维模式，是编写递归算法的核心要领。
核心要点
1. 从树的角度理解递归
核心观点：理解和编写递归算法最有效的方法是从「树」的视角去理解，其他的视角（如镜像、栈）都属于花拳绣腿。
论证例子：
- 斐波那契数列：递归结构是一棵二叉树，
fib(n) = fib(n-1) + fib(n-2) - 全排列问题：递归结构是一棵多叉树，每个节点代表一次选择
2. 编写递归的两种思维模式
所有递归算法都可以用以下两种思维模式之一来编写：
模式一：分解问题（Divide & Conquer）
特点：
- 递归函数有清晰的定义和返回值
- 利用定义计算子问题，通过子问题的解推导原问题的解
- 类似数学归纳法
适用场景：斐波那契数列、二叉树最大深度（LeetCode 104）、动态规划
代码示例（二叉树最大深度）：
// 定义：输入一个节点，返回以该节点为根的二叉树的最大深度
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
// 利用定义，计算左右子树的最大深度
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
// 根据左右子树的最大深度推出原二叉树的最大深度
return 1 + Math.max(leftMax, rightMax);
}
模式二：遍历（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();
}
}
3. 实战对比：二叉树最大深度的两种解法
同一道题可以用两种思维模式解决：
| 维度 | 分解问题思路 | 遍历思路 |
|---|---|---|
| 函数定义 | 有返回值：返回以节点为根的最大深度 | 无返回值：遍历树并记录 |
| 信息收集 | 通过返回值传递 | 通过外部变量记录 |
| 代码特点 | 利用递归定义 | 类似DFS遍历 |
| 效率 | 相同 | 相同 |
两种思维模式的延伸
| 思维模式 | 对应算法 | 说明 |
|---|---|---|
| 分解问题 | 动态规划 | 带记忆化的分解问题 |
| 分解问题 | 分治算法 | 分解+合并的典型应用 |
| 遍历 | DFS/回溯算法 | 遍历递归树收集结果 |
| 遍历 | 二叉树遍历 | 前序/中序/后序位置的应用 |
编写递归算法的步骤
- 抽象成树：这个问题是否可以抽象成一棵树结构？如果可以，就要用递归
- 选择思维模式：思考「遍历」和「分解问题」哪种更适合
- 实现：
- 分解问题：写清楚递归函数定义，利用定义计算子问题
- 遍历：用无返回值的递归函数遍历，用外部变量收集结果
相关题目
| 平台 | 题目 | 难度 | 适用思维 |
|---|---|---|---|
| LeetCode | 104. 二叉树的最大深度 | 简单 | 两种都可 |
| LeetCode | 斐波那契数列 | 简单 | 分解问题 |
| LeetCode | 46. 全排列 | 中等 | 遍历（回溯） |
相关概念
- 递归：本文的核心主题，从树的角度理解递归
- 二叉树：递归算法最天然的应用场景
- DFS：深度优先搜索，遍历思维的典型应用
- BFS：与DFS对比，广度优先搜索
- 动态规划：分解问题思维的延伸（带记忆化）
- 分治算法：分解问题思维的典型应用
- 回溯算法：遍历思维的典型应用
- 前序遍历：快速排序的思维模式（进入节点时处理）
- 后序遍历：归并排序的思维模式（离开节点时处理）
相关实体
- labuladong：本文作者，系统化讲解递归框架
- LeetCode：本文题目来源平台
总结
递归的本质是穷举——遍历一棵抽象出来的递归树。掌握「树」的视角和「遍历/分解问题」两种思维模式，就能游刃有余地编写任何递归算法。
推荐阅读
- 二叉树系列算法核心纲领：递归在二叉树中的综合应用
- 归并排序-总结：分解问题思维实例（后序遍历）
- 快速排序算法：分解问题思维实例（前序遍历）
- 滑动窗口框架：另一种算法框架思维