第二课《递归魔法与搜索树》
——DFS 为什么会自己回来？
🌟一、故事开始：神秘的递归魔法塔
1、上节课。
小骑士 DFS 学会了：
一条路走到底！
2、但是。
国王问他了一个问题：
🌟“为什么你总能自己回来？”
3、例如：
起点 ↓ A ↓ B ↓ C（1）走到 C 没路后。
小骑士居然：
自动回到 B（2）如果不能探索
再：
回到 A（3）能探索了：
继续探索别的路4、🌟国王很好奇的问：
“你怎么记住路线的？！”
5、🌟今天
我们要揭开：
DFS 最大的秘密！
🌟二、DFS 为什么能回来？
答案其实只有两个字：
🌟栈！
1、🌟回忆：什么是栈？
你们已经学过：
Stack（栈）
特点：
后进先出（LIFO）
2、例如：
放书：
先放：1号书 再放：2号书 再放：3号书拿出来时：
3号先出来 2号再出来 1号最后出来3、🌟DFS 其实也一样！
例如：
dfs(1) dfs(2) dfs(3)实际上：
系统偷偷帮你存进了“函数栈”
🌟三、真正理解递归！
1、🌟先看一个最简单例子
#include <iostream> using namespace std; void test(int x) { cout << "进入 " << x << endl; if(x == 3) return; test(x + 1); cout << "离开 " << x << endl; } int main() { test(1); return 0; }2、🌟大家猜猜输出是什么？
很多同学会认为输出为：
进入1 进入2 进入3 离开3 离开2 离开1但其实：
3、🌟真正输出：
进入1 进入2 进入3 离开2 离开14、🌟为什么没有：
离开3？
因为：
if(x == 3) return;已经直接返回了！
🌟四、程序到底是怎么运行的？
这是最关键部分！
1、🌟开始：
test(1)输出：
进入12、然后：
test(2)输出：
进入23、然后：
test(3)输出：
进入34、此时：
x == 3所以：
return;5、🌟重点来了！
程序不会结束！
而是：
回到上一层！
也就是：
test(2)继续往下执行：
cout << "离开2";6、然后：
再回到：
test(1)继续执行：
cout << "离开1";7、🌟同学们终于明白了！
递归不是：
“重新开始”
而是：
“暂停当前任务”
“去做新任务”
“做完再回来”
🌟五、DFS 的“自动返回”秘密
1、所以：
dfs(...)真正意思是：
2、🌟“我先去下一层探险”
🌟“探险结束后再回来”
3、🌟这就是 DFS 能回来的原因！
因为：
系统帮你记住了现场！
🌟六、搜索树登场！
1、现在。
我们进入 DFS 最核心思想：
🌟搜索树！
2、🌟例子：
每次+1或者+2，我们画出从数字1到4的路径。
（1）从数字：
1开始。
（2）每次可以：
+1 或者 +2直到到达 4。
3、🌟有哪些路线？
第一条
1 → 2 → 3 → 4第二条
1 → 2 → 4第三条
1 → 3 → 44、🌟把它画出来：
1 / \ 2 3 / \ \ 3 4 4 | 45、🌟这就叫：
搜索树！
🌟七、为什么“搜索树”特别重要？
因为：
1、🌟DFS 本质上：
就是：
在搜索树里不断往下走！
2、例如：
DFS 会这样搜：
1 ↓ 2 ↓ 3 ↓ 4先一条路到底！
3、然后回来：
回到2再搜：
2 → 44、🌟是不是特别像：
“树的 DFS 遍历”！
🌟八、真正开始 DFS 搜索树代码
1、🌟任务
从 1 开始。
每次：
+1
+2
到达 4。
输出所有路径。
2、🌟代码
#include <iostream> #include <vector> using namespace std; vector<int> path; void dfs(int x) { // 记录路径 path.push_back(x); // 到达终点 if(x == 4) { for(int i = 0; i < path.size(); i++) cout << path[i] << " "; cout << endl; path.pop_back(); return; } // 超过4 if(x > 4) { path.pop_back(); return; } // 两种选择 dfs(x + 1); dfs(x + 2); // 返回上一层前恢复 path.pop_back(); } int main() { dfs(1); return 0; }🌟九、真正理解这份代码！
🌟1. path 是什么？
vector<int> path;表示：
当前走过的路线。
例如：
1 → 2 → 3path 就是：
[1,2,3]🌟2. push_back
path.push_back(x);意思：
把当前点加入路径。
🌟3. 到达终点
if(x == 4)说明：
已经找到一条完整路线！
于是：
输出 path。
🌟4. 为什么要 pop_back？
这是本课最大重点！
path.pop_back();意思：
返回上一层前
撤销当前操作
🌟5. 否则会发生什么？
路径会乱掉！
例如：
本来：
1 2 3回去后：
应该恢复：
1 2🌟6.这就是：
“恢复现场”
🌟十、DFS 最重要的一句话
🌟DFS 的本质：
做选择 ↓ 进入下一层 ↓ 搜索 ↓ 返回 ↓ 恢复现场🌟十一、本课总结
🌟同学们今天学会了什么？
✅ 递归为什么会回来
因为：
函数栈！
✅ DFS 本质
DFS 是：
不断深入
再不断返回
✅ 什么是搜索树
每种选择：
都会产生新分支。
✅ DFS 在干什么
本质：
在搜索树中遍历。
✅ 为什么需要恢复现场
因为：
回到上一层后
状态必须还原。
🌟十二、课后挑战
🌟挑战1
修改代码：
从：
+1 +2改成：
+1 +3看看搜索树变化。
🌟挑战2
目标从：
4改成：
6输出所有路径。
🌟挑战3
请孩子：
自己手动画搜索树！
这是 DFS 真正开窍的关键。
🌟下节课预告
下一节：
⚔️《时间倒流术》
同学们将真正理解：
🌟什么叫“回溯”！
以及：
🌟为什么 DFS 要撤销操作！
的具体使用和介绍)
