C++ 递归、回溯与迷宫搜索｜C++ 第 18 课

Easy explanation

递归像打开一组套娃，回溯像走迷宫。

打开最大的套娃，会看到一个更小但结构相同的套娃，直到最小的不能再打开。递归函数也要有“最小情况”作为出口，其余情况把问题缩小后再次调用自己。没有出口，函数就会不停压入调用栈，最终耗尽空间。

走迷宫时，在路口选择一条路，走不通就退回路口并尝试另一条。回溯算法会记录当前选择，深入搜索，失败后撤销选择。它不是盲目重复，而是系统地枚举可能性并剪掉不可能路线。

目标 1识别递归出口和缩小步骤

目标 2画出函数调用栈与返回顺序

目标 3使用 DFS 遍历网格

目标 4实现选择、递归、撤销的回溯框架

C++ 递归、回溯与迷宫搜索通俗学习插图 — 每次只解决更小问题，返回时再把局部答案组合起来。

Core concepts

先把四个核心知识点说清楚。

01

递归出口

if (n <= 1) return 1;

最小问题直接回答，不再递归。出口必须能被所有合法输入最终到达。

02

缩小问题

return n * factorial(n - 1);

每次调用都让参数更接近出口，并使用小问题结果构造当前答案。

03

深度优先

dfs(nextRow, nextCol);

沿一条路线尽量深入，不能继续时返回，再探索其他分支。

04

撤销选择

path.pop_back();

递归返回后恢复进入前状态，让下一分支从干净状态开始。

sum(n) = n + sum(n - 1)

先写数学关系，再决定 n=0 时的直接答案。

if (visited[r][c]) return false;

访问标记防止在迷宫环路中无限来回。

choice.push_back(x); solve(); choice.pop_back();

做选择、深入、撤销是回溯最常见骨架。

if (path.size() == target) record(path);

达到完整答案时保存副本，然后返回继续寻找其他答案。

Complete examples

两个例子，把知识变成能运行的程序。

Example 1

例子一：递归计算数字各位和

n % 10 得到最后一位，n / 10 得到剩余数字。问题从多位数逐步缩小到零。

调用返回时，各层把自己保存的最后一位相加。画出 527 的三层调用能看清顺序。

每次去掉最后一位

int digitSum(int n)
{
    n = abs(n);
    if (n == 0) return 0;
    return n % 10 + digitSum(n / 10);
}

cout << digitSum(527) << '\n';
// 7 + digitSum(52)
// 7 + 2 + digitSum(5)
// 7 + 2 + 5 + digitSum(0)

digitSum(527)7 + 2 + 5结果：14

Example 2

例子二：迷宫深度优先搜索

超出边界、遇到墙或已经访问都立即失败；到达出口则成功。其余格子先标记，再递归尝试上下左右。

若需要打印路径，可以进入时加入坐标，所有方向失败后删除坐标；成功路线则保留。

标记、尝试四个方向、失败返回

bool solve(int r, int c)
{
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (maze[r][c] == '#' || visited[r][c]) return false;
    if (maze[r][c] == 'E') return true;

    visited[r][c] = true;
    path.push_back({r, c});
    int dr[] = {1, -1, 0, 0};
    int dc[] = {0, 0, 1, -1};
    for (int i = 0; i < 4; ++i)
        if (solve(r + dr[i], c + dc[i])) return true;

    path.pop_back();
    return false;
}

S..###.#...E找到从 S 到 E 的路径并标记坐标

Algorithm thinking

递归设计只关注“当前这一层负责什么”。

不要试图同时在脑中展开几十层。先假设小问题函数已经正确，再说明当前层怎样利用它。然后确认参数严格缩小并最终到达出口。用三层小输入画调用和返回，通常就能发现错误。

回溯适合搜索组合、排列和路径，但可能尝试很多可能性。可以提前检查规则，发现选择必然失败就不再深入，这叫剪枝。剪枝不能漏掉合法答案，因此必须基于确定条件。

1
定义最小问题
找出不用继续调用就能直接回答的情况。
2
保证规模缩小
每次改变参数，使它严格接近出口。
3
保存当前选择
进入下一层前记录路径、已用元素或访问状态。
4
失败后恢复
递归返回时撤销本层影响，再尝试下一个候选。

Common mistakes

这些错误很常见，学会自己排查。

1

没有可达出口

参数没有缩小或出口条件写错，会导致栈溢出。

2

忘记撤销

上一条失败路线残留在 path 中，会污染后续答案。

3

迷宫没有 visited

相邻格子互相递归，程序在环中无限调用。

4

复制巨大状态

每层按值复制网格成本很高，应使用引用并谨慎恢复修改。

本课通用调试法

先准备一个最小输入，只保留能够重现问题的几行数据；再在关键步骤输出变量值，确认程序究竟在哪一步偏离预期。编译错误从第一条开始处理，运行错误则比较“实际结果”和“期望结果”。修复后别只重跑原来的例子，还要增加空输入、边界值和错误输入，防止问题换一个形式再次出现。

Homework

第 18 课课后作业：从模仿到独立完成。

建议按顺序完成。前四题帮助巩固语法和基本操作，第五到第七题要求把多个知识点组合起来，第八题是小项目。每道题都要先写输入、处理、输出三行计划，再开始敲代码；程序运行后至少测试正常情况、边界情况和错误情况。

1

递归倒计时

从 n 输出到 1，再在返回阶段从 1 输出到 n，观察两个位置的区别。

2

幂函数

递归计算 base 的非负整数次幂，再挑战用折半方法减少调用。

3

递归回文

比较两端字符并缩小区间，忽略大小写，处理空字符串。

4

二分递归版

把上一课二分查找改成递归，参数明确表示剩余区间。

5

全排列

输出三个不同字符的所有排列，使用 used 数组并正确撤销。

6

硬币组合

用 1、2、5 组成目标金额，输出所有不重复组合并进行剪枝。

7

迷宫最短疑问

用 DFS 找到一条路，再思考为什么它不保证最短，为下一阶段算法学习留下解释。

8

四宫格项目

在 4×4 障碍地图中寻找出口，打印路径、访问格数，并处理无解地图。

本课验收标准：每个递归函数都有可达出口和严格缩小步骤；能画出至少三层调用栈；回溯代码成对执行选择与撤销；迷宫不会因环路无限递归。

提交内容应包括源代码、三组测试输入与输出、一个曾经出现的错误及修复方法。最后请用自己的话解释本课最重要的概念；如果只能照着代码念，还需要再独立重写一次核心例子。

Lesson 18 summary

递归负责深入，回溯负责干净地退回来。

base casecall stackDFSbacktrackingvisited

下一课让程序把结果保存到文件，并通过测试保证重新启动后仍能恢复正确数据。

进入第 19 课返回第 17 课查看课程大纲