第二课《递归魔法与搜索树》——DFS 为什么会自己回来一、故事开始神秘的递归魔法塔1、上节课。小骑士 DFS 学会了一条路走到底2、但是。国王问他了一个问题“为什么你总能自己回来”3、例如起点 ↓ A ↓ B ↓ C1走到 C 没路后。小骑士居然自动回到 B2如果不能探索再回到 A3能探索了继续探索别的路4、国王很好奇的问“你怎么记住路线的”5、今天我们要揭开DFS 最大的秘密二、DFS 为什么能回来答案其实只有两个字栈1、回忆什么是栈你们已经学过Stack栈特点后进先出LIFO2、例如放书先放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 开始。每次12到达 4。输出所有路径。2、代码#include iostream #include vector using namespace std; vectorint 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 是什么vectorint path;表示当前走过的路线。例如1 → 2 → 3path 就是[1,2,3]2. push_backpath.push_back(x);意思把当前点加入路径。3. 到达终点if(x 4)说明已经找到一条完整路线于是输出 path。4. 为什么要 pop_back这是本课最大重点path.pop_back();意思返回上一层前撤销当前操作5. 否则会发生什么路径会乱掉例如本来1 2 3回去后应该恢复1 26.这就是“恢复现场”十、DFS 最重要的一句话DFS 的本质做选择 ↓ 进入下一层 ↓ 搜索 ↓ 返回 ↓ 恢复现场十一、本课总结同学们今天学会了什么✅ 递归为什么会回来因为函数栈✅ DFS 本质DFS 是不断深入再不断返回✅ 什么是搜索树每种选择都会产生新分支。✅ DFS 在干什么本质在搜索树中遍历。✅ 为什么需要恢复现场因为回到上一层后状态必须还原。十二、课后挑战挑战1修改代码从1 2改成1 3看看搜索树变化。挑战2目标从4改成6输出所有路径。挑战3请孩子自己手动画搜索树这是 DFS 真正开窍的关键。下节课预告下一节⚔️《时间倒流术》同学们将真正理解什么叫“回溯”以及为什么 DFS 要撤销操作