递归是很多人学习路上的一道坎。

它的反直觉之处在于：你没法在脑子里完整地展开整个递归过程，越想越晕。

但其实递归有套路可循，掌握了套路，就能”以不变应万变”。

递归的三要素

任何递归问题，都必须明确三件事：

  1. 递归的定义：这个函数要做什么？（返回什么、有什么效果）
  2. 递归的终止条件：什么时候不再递归，直接返回？
  3. 递归的递推关系：怎么把大问题拆成子问题？

以经典的斐波那契为例：

1
2
3
4
int fib(int n) {
    if (n <= 1) return n;          // 终止条件
    return fib(n-1) + fib(n-2);    // 递推关系
}

想递归的正确姿势

新手最容易犯的错，是在脑子里展开递归树——“fib(5) 调用 fib(4)，fib(4) 又调用 fib(3)……”，然后彻底乱掉。

正确姿势是只关注当前这一层：

  1. 假设子问题已经解决了（相信递归）
  2. 只思考”怎么用子问题的结果，得到当前问题的结果”
  3. 然后补上终止条件

就像数学归纳法：假设 n-1 成立，证明 n 成立，再验证 n=1 成立。你不需要展开所有步骤。

递归的本质是”栈”

理解递归，一定要理解底层：递归就是系统帮你维护一个调用栈。

每次函数调用，系统把当前状态压栈；函数返回，弹栈恢复状态。

所以：

  • 递归太深 → 栈溢出（StackOverflow）
  • 递归的空间复杂度 = 递归深度（栈的层数）
  • 任何递归都能改成”显式栈 + 循环”的迭代写法

这也解释了为什么尾递归能被优化——如果递归调用是函数的最后一步，那就不需要保存当前栈帧，可以复用，栈就不会无限增长。

回溯：递归的进阶应用

回溯是”试错式”的递归：一条路走不通，就撤销上一步的选择，退回来换另一条路。

经典例子：全排列。求 [1, 2, 3] 的所有排列。

回溯的通用模板：

1
2
3
4
5
6
7
8
9
10
11
void backtrack(路径, 选择列表) {
    if (满足结束条件) {
        收集结果;
        return;
    }
    for (选择 in 选择列表) {
        做出选择;
        backtrack(路径, 选择列表);
        撤销选择;   // 关键：回溯
    }
}

对应全排列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void backtrack(int[] nums, List<Integer> path, boolean[] used) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));  // 收集结果
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;              // 跳过已选
        used[i] = true;                     // 做出选择
        path.add(nums[i]);
        backtrack(nums, path, used);        // 递归
        path.remove(path.size() - 1);       // 撤销选择
        used[i] = false;                    // 撤销标记
    }
}

核心就是那句 “撤销选择”——回溯的”回溯”二字，指的就是这一步。

剪枝：回溯的优化

回溯本质是暴力搜索，最坏情况复杂度是指数级的。所以必须剪枝——提前排除不可能的分支。

比如 N 皇后问题：放皇后时，如果某列已经被攻击，就直接跳过，不再往下递归。这就是剪枝。

剪枝是回溯算法”能不能在数据稍大时还能跑”的关键。回溯 + 剪枝 = 有效率的暴力搜索。

递归的经典应用

  • 树的遍历（前中后序）——天然递归
  • 分治算法（快排、归并）——把问题拆成子问题
  • 回溯（全排列、组合、N 皇后、数独）——试错 + 撤销
  • 动态规划（自顶向下 + 备忘录）——递归 + 缓存

写在最后

递归的两个心法，帮你迈过这道坎：

  1. 相信递归——别展开，只关注当前层
  2. 明确三要素——定义、终止、递推

回溯则是”递归 + 撤销”，模板固定，套着写就行。

下一篇聊并发编程基础——这是把”单线程的确定性”打碎、进入”多线程的不确定性”的重要一课。