A 班 第 6 课：专题六·递归与深度优先搜索（DFS）

适用对象： 完成第 5 课（动态规划入门）的同学 使用方式： 自学讲义，Dev-C++ 5.11，练习按考场 freopen 格式写 学完本课，你应该能：

  1. 说清楚递归三要素，看懂一段递归代码的执行顺序
  2. 默写 DFS 的通用框架，并解释"回溯"这一步在干什么
  3. 分清排列型、组合型、网格型三种搜索，各独立做出一道题

1. 递归：函数自己调用自己（15 分钟）

上节课讲 DP 时说过一句话：暴力搜索会把同一个小问题反复算很多遍。今天先把那个"暴力搜索"本身讲清楚——它的地基就是递归。

递归就是一个函数在自己的函数体里调用自己。最小的例子是阶乘：

#include <bits/stdc++.h>
using namespace std;

int fac(int n) {
    if (n == 1) return 1;        // ① 边界条件
    return n * fac(n - 1);       // ② 递推关系
}

int main() {
    cout << fac(5) << endl;
    return 0;
}

输出：120

fac(5) 要算 5 * fac(4)，fac(4) 又要算 4 * fac(3)……一直递到 fac(1) 碰到边界返回 1，再一层层乘回来。"递下去"和"归回来"合起来就叫递归。

递归三要素（和上节课的 DP 三件套一样，写代码前先在草稿纸上想清楚这三条）：

三要素 要回答的问题 阶乘的例子
① 边界条件 递到什么时候就不往下递了？ n == 1 时直接返回 1
② 递推关系 大问题怎么用更小的同类问题表示？ fac(n) = n * fac(n-1)
③ 规模递减 每次调用的参数是不是在朝边界靠近？ n 每次减 1，一定能走到 1

⚠️ 三条里最容易漏的是 ①。 没有边界条件的递归会一直往下递，直到把系统给程序的栈空间撑爆——运行时直接崩溃（栈溢出），编译器一个字都不会提醒你。

递归和 DP 的关系（回扣上节课）

上节课的爬楼梯（一次上 1 级或 2 级），不查表、直接照着 f(n) = f(n-1) + f(n-2) 递归也能写出来。答案和上节课一样是 89，但它慢得离谱——我们把每个 f(i) 被调用的次数数出来看看：

#include <bits/stdc++.h>
using namespace std;

int cnt[25];

int f(int n) {
    cnt[n]++;
    if (n == 1) return 1;        // ① 边界，和上节课的初始状态一模一样
    if (n == 2) return 2;
    return f(n - 1) + f(n - 2);  // ② 递推关系
}

int main() {
    cout << f(10) << endl;
    for (int i = 1; i <= 10; i++)
        cout << "f(" << i << ") 被调用了 " << cnt[i] << " 次" << endl;
    return 0;
}

输出：

89
f(1) 被调用了 21 次
f(2) 被调用了 34 次
f(3) 被调用了 21 次
f(4) 被调用了 13 次
f(5) 被调用了 8 次
f(6) 被调用了 5 次
f(7) 被调用了 3 次
f(8) 被调用了 2 次
f(9) 被调用了 1 次
f(10) 被调用了 1 次

答案 89 是对的，但代价惊人：只算到 10，f(2) 就已经被重复算了 34 遍、f(3) 被算了 21 遍。n 再大一点就是天文数字（O(2ⁿ)）。而上节课那份 DP 写法算 f[10] 只做了 8 次加法。

📝 一句话总结这两课的关系： 同样是"把大问题拆成小问题"——

2. DFS 框架与排列型搜索：全排列（25 分钟）

DFS（深度优先搜索） 的思路特别像走迷宫：选一条路一直往前走，走到死路或走到终点，就退回上一个路口换另一条路。这个"退回来"的动作叫 回溯。

先把框架背下来，本课三道题用的都是它，只有中间那几行不一样：

void dfs(第几步) {
    if (走完了) { 处理答案; return; }        // ① 边界
    for (每一种可能的选择) {
        if (这个选择不能用) continue;         // ② 剪枝
        做出选择（打标记）;
        dfs(下一步);                          // ③ 递归
        撤销选择（取消标记）;                  // ④ 回溯 ← 最容易漏
    }
}

第一个例子：输出 1~n 的全排列。 比如 n = 3 要输出 1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1 六行。

"还没用过"用一个 bool vis[] 标记数组记录，"当前已经挑了哪些"用 path[] 记录：

#include <bits/stdc++.h>
using namespace std;

int n = 3;
int path[15];        // path[step] = 第 step 位放的数字
bool vis[15];        // vis[i] = true 表示数字 i 已经被用过了

void dfs(int step) {
    if (step > n) {                                       // ① 三位都填满了
        for (int i = 1; i <= n; i++) cout << path[i] << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;                             // ② 用过了，跳过
        vis[i] = true;                                    //    选它
        path[step] = i;
        dfs(step + 1);                                    // ③ 去填下一位
        vis[i] = false;                                   // ④ 回溯：把它放回去
    }
}

int main() {
    dfs(1);
    return 0;
}

输出：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

为什么必须有第 ④ 步（本课最重要的一条）

跟着 n = 3 手工走一遍，注意看 vis 的变化：

dfs(1) 选 1 → vis[1]=T
  dfs(2) 选 2 → vis[2]=T
    dfs(3) 选 3 → 输出 1 2 3，返回
    ← 回溯：vis[3]=F        （3 放回去了，下面才可能再用它）
  ← 回溯：vis[2]=F          （2 放回去了）
  dfs(2) 选 3 → vis[3]=T    （这一步只有在 3 被放回去之后才做得成）
    dfs(3) 选 2 → 输出 1 3 2

dfs() 这一行返回之后，程序要回到"调用它之前"的状态，才能安心尝试下一个选择。 这就是"恢复现场"。少写这一行，vis 会一直是 true，后面所有分支全部被堵死。

⚠️ 实测： 把上面代码里的 vis[i] = false; 删掉，n = 3 的输出只剩一行 1 2 3——因为 1、2、3 全被永久标记成"用过"，一条分支都走不下去了。

📝 口诀：选了要还，标了要清。 写完 dfs(...) 那一行，手指立刻往下移一行，把撤销写上，再回头写别的。

3. 组合型搜索：选数（洛谷 P1036，NOIP 2002 普及组 T2）（20 分钟）

题意： 已知 n 个整数 x₁, x₂, …, xₙ，以及一个整数 k（k < n）。从这 n 个整数中任选 k 个相加，求和为质数的选法共有多少种。

样例（洛谷 P1036 官方样例）：

输入样例：
4 3
3 7 12 19

输出样例：
1

四种选法：3+7+12=22、3+7+19=29、3+12+19=34、7+12+19=38，只有 29 是质数，所以答案是 1。

数据范围： 1 ≤ n ≤ 20，k < n。

📝 每个数的上界请自己去洛谷题面的"说明/提示"里看一眼再动手——考场上先读数据范围、再决定用 int 还是 long long，这个习惯比任何算法都重要。本题按 int 写够用。

和全排列的唯一区别：下标只增不减

这题选出来的是组合不是排列——{3, 7, 19} 和 {7, 3, 19} 是同一种选法，只能算一次。全排列的写法会把它数 6 遍。

解决办法只有一个字的改动：规定每次只能从"上一个选中位置的后面"继续挑。所以 dfs 要多带一个参数 start：

#include <bits/stdc++.h>
using namespace std;

int n = 4, k = 3;
int x[25] = {0, 3, 7, 12, 19};        // 直接用官方样例的数据，方便你跟着跑
int ans = 0;

bool isPrime(int v) {
    if (v < 2) return false;
    for (int i = 2; i * i <= v; i++)
        if (v % i == 0) return false;
    return true;
}

void dfs(int cnt, int start, int sum) {       // 已选 cnt 个，从第 start 个开始挑，当前和 sum
    if (cnt == k) {                           // ① 选够 k 个了
        if (isPrime(sum)) ans++;
        return;
    }
    for (int i = start; i <= n; i++)          // ← 从 start 开始，不是从 1 开始
        dfs(cnt + 1, i + 1, sum + x[i]);      // ← 下一层从 i + 1 开始
}

int main() {
    dfs(0, 1, 0);
    cout << ans << endl;
    return 0;
}

输出：1

📝 这段代码没有 vis 数组、也没有显式的"撤销"。 因为 sum + x[i] 是当作参数传下去的，函数返回时那个临时的 sum 自动就没了——回溯被参数传递自动完成了。这两种写法（全局变量 + 手动撤销 / 参数传递 + 自动回溯）都要会看，考场上哪个顺手用哪个。

📝 isPrime 里的 i * i <= v 就是"试除到 √v"，写成 i * i <= v 比 i <= sqrt(v) 更稳（不涉及浮点数误差），是竞赛标准写法。

估一下规模： n = 20 时组合数最多是 C(20,10) = 184756 种，每种做一次 O(√sum) 的质数判断，完全跑得动。

⚠️ 实测： 把 for (int i = start; ...) 误写成 for (int i = 1; ...)，官方样例的答案会从 1 变成 21——同一个组合按不同顺序被反复数了。

4. 网格型搜索：迷宫（洛谷 P1605）（20 分钟）

题意： 给一个 N × M 的方格迷宫，其中有 T 处障碍不能通过。从起点走到终点，每次只能上下左右移动一格，每个格子最多经过一次，问一共有多少种走法。

样例（洛谷 P1605 官方样例）：

输入样例：
2 2 1
1 1 2 2
1 2

输出样例：
1

（2×2 的迷宫，起点 (1,1)，终点 (2,2)，(1,2) 是障碍。只剩 (1,1)→(2,1)→(2,2) 这一条路。）

数据范围： 1 ≤ N, M ≤ 5，1 ≤ T ≤ 10。格子最多 25 个，暴力搜完全够。

新工具：方向数组

"上下左右四种走法"如果写四个 if 会很啰嗦，标准做法是把四个方向存成两个数组，用一个循环搞定：

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
// 第 d 个方向：新位置 = (x + dx[d], y + dy[d])
//   d=0 → (x,   y+1) 右
//   d=1 → (x,   y-1) 左
//   d=2 → (x+1, y  ) 下
//   d=3 → (x-1, y  ) 上

📝 方向数组是网格搜索的标配，背下来。 以后做八个方向的题就扩成 dx[8]、dy[8]。

框架和全排列一模一样，只是"下一步能走哪"换成了"四个方向里没出界、没障碍、没走过的那些"：

#include <bits/stdc++.h>
using namespace std;

int N, M, T, sx, sy, fx, fy, ans = 0;
bool block[10][10], vis[10][10];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void dfs(int x, int y) {
    if (x == fx && y == fy) { ans++; return; }        // ① 到终点了，记一种走法
    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx < 1 || nx > N || ny < 1 || ny > M) continue;   // ② 出界
        if (block[nx][ny] || vis[nx][ny]) continue;           // ② 障碍 / 走过了
        vis[nx][ny] = true;                                   //    走过去
        dfs(nx, ny);                                          // ③
        vis[nx][ny] = false;                                  // ④ 回溯：退回来
    }
}

int main() {
    cin >> N >> M >> T >> sx >> sy >> fx >> fy;
    for (int i = 1; i <= T; i++) {
        int a, b;
        cin >> a >> b;
        block[a][b] = true;
    }
    vis[sx][sy] = true;        // 起点也算走过了，别忘
    dfs(sx, sy);
    cout << ans << endl;
    return 0;
}

拿官方样例跑，输出 1。

⚠️ 这道题的官方样例弱得很危险。 把 vis[nx][ny] = false; 那行删掉（也就是忘了回溯），官方样例照样输出 1，你会以为自己写对了，一提交全错。

自己造个大一点的样例验一下——3×3 无障碍、从 (1,1) 走到 (3,3)：

3 3 0
1 1 3 3

正确答案是 12；忘了回溯的版本会输出 1。

📝 考场经验：过了样例 ≠ 写对了。 尤其是搜索题，官方样例经常小到掩盖 bug。自己手动构造一个"能手算出答案的稍大数据"，是最划算的一分钟。

📝 三道题用的是同一个框架，请对照着看这张表——变的只有"下一步能走哪"：

一层枚举什么 怎么防重复 边界（什么时候记答案）
全排列（排列型） 所有还没用过的数 vis[] 标记 填满 n 位
选数（组合型） 第 start 个到第 n 个 下标只增不减 选够 k 个
迷宫（网格型） 四个方向 vis[][] 标记 走到终点格

5. 读错误：3 个典型坑（10 分钟）

错误 1：忘了回溯

for (int i = 1; i <= n; i++) {
    if (vis[i]) continue;
    vis[i] = true;
    path[step] = i;
    dfs(step + 1);
    // ← 这里漏了 vis[i] = false;
}

标记只加不减，所有分支都被堵死。全排列 n = 3 只会输出一行 1 2 3；迷宫 3×3 无障碍那个样例会从 12 变成 1。编译、运行都正常，就是答案小得离谱。

📝 搜索题调不出来，第一件事永远是检查回溯写了没有。

错误 2：忘了边界条件

void dfs(int step) {
    // ← 这里漏了 if (step > n) { ...; return; }
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        vis[i] = true;
        dfs(step + 1);
        vis[i] = false;
    }
}

递归永远不返回，栈空间被撑爆 → 程序直接崩溃（评测机上表现为运行时错误 RE，或者段错误 Segmentation fault）。编译器不会有任何提示。

📝 写 void dfs( 这一行的时候，就顺手先把 if (...) return; 写好，再写下面的循环。

错误 3：组合型忘了用 start

void dfs(int cnt, int start, int sum) {
    if (cnt == k) { if (isPrime(sum)) ans++; return; }
    for (int i = 1; i <= n; i++)          ← 应该是 i = start
        dfs(cnt + 1, i + 1, sum + x[i]);
}

同一个组合被按不同顺序反复数。选数官方样例的正确答案是 1，这样写会输出 21。

📝 判断标准很简单：题目问"选法/组合"就要用 start，问"排列/顺序"才从 1 开始配 vis。 读完题先想清楚这一点。

6. 本课练习

⭐ 基础题 1：全排列问题（洛谷 P1706 原题，文件名 t1.cpp，freopen perm.in/perm.out）

按字典序输出 1 到 n 的所有不重复排列，每行一个。1 ≤ n ≤ 9。

⚠️ 注意输出格式：每个数字占 5 个场宽（右对齐补空格）。用 cout << setw(5) << x; 就行，setw 在 <iomanip> 里，而 bits/stdc++.h 已经把它包含进来了，不用额外写头文件。

输入样例：
3

输出样例：
    1    2    3
    1    3    2
    2    1    3
    2    3    1
    3    1    2
    3    2    1
参考答案 
#include <bits/stdc++.h>
using namespace std;

int n, path[15];
bool vis[15];

void dfs(int step) {
    if (step > n) {
        for (int i = 1; i <= n; i++) cout << setw(5) << path[i];
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        vis[i] = true;
        path[step] = i;
        dfs(step + 1);
        vis[i] = false;
    }
}

int main() {
    freopen("perm.in", "r", stdin);
    freopen("perm.out", "w", stdout);

    cin >> n;
    dfs(1);
    return 0;
}

为什么输出天然就是字典序？因为内层 for 是从小到大枚举 i 的——每一位都先试小的，自然就按字典序出来了。⚠️ setw(5) 只对紧跟着的那一个输出生效，所以要写在循环里面每个数字前面，不能只写一次。

⭐⭐ 实战题 2：迷宫（洛谷 P1605 原题，文件名 t2.cpp，freopen maze.in/maze.out）

题面见上文例题三，1 ≤ N, M ≤ 5，1 ≤ T ≤ 10。

输入样例：
2 2 1
1 1 2 2
1 2

输出样例：
1

⚠️ 交之前一定要用 3 3 0 / 1 1 3 3（答案 12）自测一遍——官方样例查不出忘回溯的错。

参考答案 
#include <bits/stdc++.h>
using namespace std;

int N, M, T, sx, sy, fx, fy, ans = 0;
bool block[10][10], vis[10][10];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void dfs(int x, int y) {
    if (x == fx && y == fy) { ans++; return; }
    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx < 1 || nx > N || ny < 1 || ny > M) continue;
        if (block[nx][ny] || vis[nx][ny]) continue;
        vis[nx][ny] = true;
        dfs(nx, ny);
        vis[nx][ny] = false;
    }
}

int main() {
    freopen("maze.in", "r", stdin);
    freopen("maze.out", "w", stdout);

    cin >> N >> M >> T >> sx >> sy >> fx >> fy;
    for (int i = 1; i <= T; i++) {
        int a, b;
        cin >> a >> b;
        block[a][b] = true;
    }
    vis[sx][sy] = true;
    dfs(sx, sy);
    cout << ans << endl;
    return 0;
}

三个容易漏的点：起点要先 vis[sx][sy] = true（否则路径会绕回起点）；ans++ 之后要 return（终点不用再往外走）；数组开到 [10][10] 留够余量。

⭐⭐⭐ 冲刺题 3：选数（洛谷 P1036 原题，NOIP 2002 普及组 T2，文件名 t3.cpp，freopen select.in/select.out）

题面见上文例题二。第一行两个整数 n、k（1 ≤ n ≤ 20，k < n），第二行 n 个整数。输出和为质数的选法数。

输入样例：
4 3
3 7 12 19

输出样例：
1
参考答案 
#include <bits/stdc++.h>
using namespace std;

int n, k, x[25], ans = 0;

bool isPrime(int v) {
    if (v < 2) return false;
    for (int i = 2; i * i <= v; i++)
        if (v % i == 0) return false;
    return true;
}

void dfs(int cnt, int start, int sum) {
    if (cnt == k) {
        if (isPrime(sum)) ans++;
        return;
    }
    for (int i = start; i <= n; i++)
        dfs(cnt + 1, i + 1, sum + x[i]);
}

int main() {
    freopen("select.in", "r", stdin);
    freopen("select.out", "w", stdout);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> x[i];
    dfs(0, 1, 0);
    cout << ans << endl;
    return 0;
}

写完检查三件事：内层是 i = start 不是 i = 1 吗？下一层传的是 i + 1 吗？isPrime 里 v < 2 的情况处理了吗（1 和 0 都不是质数）？

本课要点速查

递归三要素：

内容
① 边界条件 递到什么时候停，漏了就栈溢出
② 递推关系 大问题怎么用更小的同类问题表示
③ 规模递减 每次调用的参数必须朝边界靠近

DFS 通用框架（默写下来）：

void dfs(第几步) {
    if (走完了) { 处理答案; return; }
    for (每一种可能的选择) {
        if (这个选择不能用) continue;
        做出选择（打标记）;
        dfs(下一步);
        撤销选择（取消标记）;      // 回溯，最容易漏
    }
}

三种搜索的区别（只差"一层枚举什么"）：

类型 循环怎么写 防重复靠什么
排列型（全排列） for (i = 1; i <= n; i++) + if (vis[i]) continue; vis[] 标记 + 撤销
组合型（选数） for (i = start; i <= n; i++)，下一层传 i + 1 下标只增不减
网格型（迷宫） for (d = 0; d < 4; d++) 配方向数组 vis[][] 标记 + 撤销

方向数组模板：

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

易错点： 忘回溯 → 答案小得离谱且不报错；忘边界 → 栈溢出崩溃；组合型忘 start → 答案偏大；网格题忘了把起点标成走过；setw(5) 只对紧跟的一个输出生效。

口诀：选了要还，标了要清；过了样例不算过，自己造个大的再交。

以后学： BFS（宽度优先搜索）与队列、剪枝优化、记忆化搜索（DFS 存答案 = DFS 和 DP 的结合）、图上的 DFS 与连通块。今天这个框架到那时候一个字都不用改。

结束前的自我检查

  1. 不看讲义，默写出 DFS 的四步框架，并说出哪一步最容易漏
  2. 用一句话说清楚：什么样的题要用 start，什么样的题要用 vis
  3. 练习 1、2 全部通过；⭐⭐⭐ 选数能独立写出来
  4. 把练习 2 的回溯那一行删掉跑一遍 3 3 0 / 1 1 3 3，亲眼看看答案从 12 变成 1
  5. 向别人解释：同样是 f(n) = f(n-1) + f(n-2)，为什么裸递归算爬楼梯那么慢，而上节课的 DP 那么快