一起动脑筋 · 先看一个小故事
机器人走迷宫，在路口选一条路。遇到死胡同时，它沿任务记录退回岔路，再试没走过的方向。
把过程摊开来看
- 进入格子标记已访问
- 尝试邻格递归探索
- 走不通返回路口
- 继续换未探索的方向
递归可以表达“探索这个位置附近的路”。
已访问标记帮助避免在环路里来回走。若记录当前路径，退回时还要按所用算法更新路径记录。
01迷宫为什么和递归有关系？
站在一个格子上时，可以做这样的思考：
“我先走到一个相邻格子，然后把‘从那里继续找出口’交给同一个方法。”
这正是把问题变成更小同类问题。
02当前位置要做哪些事？
检查出口
已经到终点了吗？
标记当前位置
防止反复走回来。
尝试方向
上、下、左、右。
失败就返回
换另一条路继续试。
03一个简化的递归模型
bool dfs(int row, int col) {
if (到达出口) {
return true;
}
标记当前位置已经访问;
for (四个方向) {
if (新位置可以走且没有访问) {
if (dfs(新位置)) {
return true;
}
}
}
return false;
}这里用的是伪代码式 C++，重点先理解执行过程，而不是背语法模板。
04走进去时调用栈怎样变化？
位置 C位置 B位置 A起点
每走进一个新的位置，就像进入更深一层调用。
05死路为什么会“退回来”？
如果当前位置所有方向都走不通，当前这一层返回 false。
控制流就回到上一层，上一层继续尝试下一个方向。
走进去→发现死路↑退回上一层→换一条路
这就是回溯（backtracking）的基本直觉。
06为什么必须记录“已经来过”？
迷宫里可能有环。
如果 A 能走到 B，B 又能走回 A，而我们不记录访问状态，就可能：
A→B→A→B...
07递归一定是迷宫最快的方法吗？
不一定。
递归 DFS 很适合判断“有没有一条路”、遍历所有可达位置等任务；如果要找无权图中的最短步数，BFS 往往更合适。
后面的“搜索与效率”专题会正式比较 DFS 和 BFS。
你已经知道了什么
- 迷宫搜索可以把“从当前位置找出口”递归成“从下一个位置继续找出口”。
- 进入新位置对应更深一层调用。
- 死路返回上一层，再尝试其他方向，这就是回溯直觉。
- 必须记录已访问位置，避免在环中无限重复。
- 递归 DFS 不一定适合所有搜索目标，最短路等问题还可能使用 BFS。
本专题完成：下一专题进入“数据结构”。
轮到你来试一试
迷宫里有一圈通道，如果从不记录访问过的格子，会怎样？
想好了吗？点开看解释
可能绕圈重复探索。要明确已访问状态，以及什么时候保留或撤销它。