递归与回溯

一、递归

1. 什么是递归

递归就是函数自己调用自己。把一个大的问题拆成规模更小的同类问题，直到问题小到可以直接解决为止。

一个递归函数必须包含两部分：

1. 终止条件（base case）：什么时候不再递归，直接返回结果；
2. 递归关系（recurrence）：如何把当前问题转化为规模更小的同类问题。

def factorial(n):
    if n == 0:          # 终止条件
        return 1
    return n * factorial(n - 1)   # 递归关系

2. 递归是怎么执行的

以 factorial(3) 为例：

factorial(3)
  → 3 * factorial(2)
        → 2 * factorial(1)
              → 1 * factorial(0)
                    → 1        ← 终止条件，开始返回
              ← 1 * 1 = 1
        ← 2 * 1 = 2
  ← 3 * 2 = 6

递归调用会一层层压入调用栈，直到遇到终止条件，然后一层层返回。栈的深度就是递归的层数。

3. 递归的三要素

要素	含义	例子
终止条件	什么时候停止递归	n == 0
当前层逻辑	这一层要做什么	n * ...
递归方向	下一层规模如何变小	factorial(n - 1)

写递归的关键：不要试图在脑子里展开每一层。只要相信「下一层会正确返回」，然后处理好「当前层做什么」即可。

4. 递归的两个方向

• 自顶向下：从大问题出发，不断拆成小问题，直到终止条件。典型：factorial、斐波那契。
• 自底向上：从小问题出发，不断合并成大问题。典型：动态规划。

---

二、从递归到回溯

1. 递归 ≠ 回溯

• 递归：一种编程技巧，函数自己调用自己；
• 回溯：一种算法思想，用递归遍历所有可能的解，并在搜索过程中「撤销」上一步的选择。

回溯一定用递归实现，但递归不一定都是回溯。

2. 回溯的核心思想

把求解过程想象成在一棵决策树上搜索：

• 每个节点代表一个中间状态；
• 每条边代表一个选择；
• 从根出发，每做一次选择就往下走一层；
• 走到叶子节点，要么得到一个解，要么发现这条路走不通，就「退回来」换别的选择。

回溯 = 选择 → 递归 → 撤销选择

3. 回溯模板

def backtrack(路径, 选择列表):
    if 满足终止条件:
        记录答案
        return

    for 选择 in 选择列表:
        做出选择          # 路径.append(选择)
        backtrack(路径, 新的选择列表)
        撤销选择          # 路径.pop()

核心就是三行：

路径.append(选择)       # 做选择
backtrack(...)          # 进入下一层
路径.pop()              # 撤销选择

4. 为什么必须「撤销选择」

因为 路径 是一个共享变量，它在整个递归过程中被反复使用。

• append 表示“走这一步”，把选择加入当前路径；
• pop 表示“退回来”，把上一步的选择移除，恢复进入这一层之前的状态。

如果不 pop，路径会越积越长，后面所有分支都会带着前面分支的选择，结果全错。

5. 为什么记录答案时要复制

ans.append(路径)       # 错：存的是引用
ans.append(路径[:])    # 对：存的是副本

Python 中变量存的是对象的引用，ans.append(路径) 只是把同一个列表对象存进 ans。后续回溯时 路径 会被修改，ans 里存的内容也跟着变。所以必须用 路径[:] 或 list(路径) 存一份副本。

---

三、回溯的常见题型

1. 子集 / 组合

从一组数中选出若干个数，要求满足某些条件。

例题：LeetCode 78 子集、39 组合总和、77 组合。

模板：

def dfs(start, path):
    ans.append(path[:])          # 每个节点都是一个解
    for i in range(start, n):
        path.append(nums[i])
        dfs(i + 1, path)         # 组合：下一层从 i+1 开始
        path.pop()

关键点：

• start 控制“从哪个位置开始选”，避免重复；
• 如果允许重复选同一个数，dfs(i, path)，i 不变；
• 如果每个数只能选一次，dfs(i + 1, path)。

2. 排列

从一组数中选出所有数，顺序不同算不同解。

例题：LeetCode 46 全排列、47 全排列 II。

模板：

def dfs(path):
    if len(path) == n:
        ans.append(path[:])
        return
    for i in range(n):
        if used[i]:
            continue
        used[i] = True
        path.append(nums[i])
        dfs(path)
        path.pop()
        used[i] = False

关键点：

• 用 used 数组标记哪些数已经选过；
• 每层从头遍历，但要跳过已用的数。

3. 棋盘类搜索

在网格或棋盘上搜索路径。

例题：LeetCode 79 单词搜索、51 N 皇后。

模板：

def dfs(i, j, path):
    if 满足终止条件:
        return True
    for 方向 in 四个方向:
        ni, nj = i + dx, j + dy
        if 越界 or 已访问 or 不满足条件:
            continue
        标记已访问
        if dfs(ni, nj, path):
            return True
        撤销标记
    return False

---

四、回溯的执行过程

以 LeetCode 39 组合总和为例：candidates = [2,3,6,7]，target = 7。

搜索树：

                    []
          /          |        \
        [2]         [3]      [6]   [7]
       / | \         |        |
   [2,2][2,3][2,6] [3,3]   [6,...]
    /     |
[2,2,2] [2,3,3]←答案
   |
[2,2,3]←答案

具体走一遍：

1. 选 2 → path = [2]，target = 5
2. 选 2 → path = [2, 2]，target = 3
3. 选 3 → path = [2, 2, 3]，target = 0 → 记录答案，返回
4. pop 掉 3 → path = [2, 2]，尝试其他数
5. 选 6 超了，跳过；选 7 超了，跳过
6. pop 掉 2 → path = [2]，尝试 3
7. 选 3 → path = [2, 3]，target = 2
8. 选 2 → target = 0 → 记录答案 [2, 3, 2]？不对，这里下一层要从 3 开始选，避免重复
9. …继续搜索

关键点：每次 pop 就是“退回到上一个节点”，换一条分支继续走。

---

五、递归 + 回溯的思维框架

1. 四步分析法

写回溯题时，按下面四步思考：

步骤	问题	例子（组合总和）
1. 定义状态	递归函数参数表示什么？	dfs(target, path, idx)：剩余目标、当前路径、从哪个位置开始选
2. 终止条件	什么时候记录答案/返回？	target == 0 记录答案；target < 0 或 idx == n 返回
3. 选择列表	当前层可以做什么选择？	从 idx 开始，每个数都可以选或不选
4. 撤销选择	递归返回后如何恢复状态？	path.pop()

2. 两个常见优化

• 排序 + 剪枝：先对 candidates 排序，遇到 candidates[i] > target 时直接 break，后面的更大，不可能满足；
• 去重：排序后，如果 i > start and nums[i] == nums[i-1]，跳过，避免重复解。

3. 复杂度分析

• 时间复杂度：取决于搜索树的节点数，通常是 $O(2^n)$、$O(n!)$ 或 $O(S)$（$S$ 为所有解的长度之和）；
• 空间复杂度：$O(n)$，取决于递归栈深度。

---

六、常见错误

错误	原因	修复
答案全是 [] 或错乱	ans.append(path) 存的是引用	改成 ans.append(path[:])
答案有重复组合	下一层从 0 开始，或没去重	组合题下一层从 i 或 i+1 开始；排序后跳过相同元素
无限递归	终止条件缺失或错误	检查终止条件，确保每层问题规模在缩小
路径没有恢复	忘了 pop	递归返回后立即 pop
结果包含不完整路径	记录答案的时机不对	在终止条件满足时记录，而不是中途记录

---

七、总结

递归

• 函数自己调用自己，必须有终止条件和递归关系；
• 关键是「相信下一层会正确返回」，专注当前层逻辑；
• 底层用调用栈实现。

回溯

• 本质是在决策树上做 DFS；
• 核心模板：选择 → 递归 → 撤销；
• 路径是共享变量，记录答案要复制，递归返回要撤销；
• 适用于子集、组合、排列、棋盘搜索等「枚举所有可能」的问题。

一句话记忆

递归是「自己调用自己」，回溯是「走不通就退回来，换一条路再走」。