GESP 七级 · GESP 202606 C++ 七级 第 21 题

泛洪算法可以用递归 DFS 实现，但地图很大时可能由于递归层数过深导致调用栈溢出等运行时错误。

DFS 使用栈（或递归），沿一条路径走到底再回溯，适合遍历所有可能状态。注意回溯时的状态恢复。

DFS 递归遍历时注意状态回溯（恢复现场）。图遍历需要visited数组避免重复访问和死循环。

【考点】递归与迭代｜调用栈溢出

1. 考纲定位 本题考查 GESP 七级"算法"模块的递归与栈溢出概念。命题人专门设此题为拦路虎——卡住那些只会背"递归能解决所有问题"结论的考生，强制其意识到递归深度与调用栈容量的硬约束。

2. 解题思维 看到"递归 DFS"立刻联想泛洪算法的经典实现：从起点出发，层层深入相邻格子。关键观察在于"递归深度"与"调用栈容量"的硬约束——每层递归都要压栈，大地图递归层数可能超过系统栈上限（如 1MB 栈空间），必然触发栈溢出错误。这类题通法是：凡涉及大结构递归遍历的，优先考虑迭代实现。

3. 陷阱拆解 若死记"递归优雅"就选错——命题人利用"递归必然可行"的思维惯性设陷阱。绝对化表述"递归 DFS 实现"看似无懈可击，实则暗藏"地图很大"的边界条件。只背结论不理解本质，就会忽略调用栈的物理限制，掉进这个看似无懈可击的陷阱。

4. 反命题思维 若把"递归 DFS"改为"栈迭代实现"，答案仍为正确——命题人真正想考的是你对递归局限性的认知，而非具体实现方式。