DFS的递归本质分析

1. 递归的来源——DFS 本质

DFS（深度优先搜索）的核心思想是：

“从一个节点出发，把所有可能深入的路径都走一遍，直到没有新的节点可走，再回溯到上一层节点。”

• “把所有可能深入的路径都走一遍”——这是递归的自然体现：每次深入访问一个节点，然后再访问它的子节点，就像函数自己调用自己。

• 回溯本质就是函数执行完子节点的递归后返回上一层。

换句话说，递归是实现深度优先遍历最自然的方法。

如果不想递归，也可以用栈模拟，但逻辑上是一样的：每访问一个节点，就把它的子节点压入栈，逐个访问。

2. 循环遍历邻居——处理每个分支

每个节点可能有多个相邻节点（孩子或者邻居），而 DFS 需要遍历它们每一个。

• 循环 for (int v : g[u]) 就是“枚举所有可能的下一步”，即遍历每个子节点。

• 对每个子节点递归调用 DFS，深度+1。

思路理解：

1. 当前节点 u 的邻居有 v1, v2, v3…

2. 每个邻居都可能是新的分支，需要进入它们的子树。

3. 所以循环遍历邻居，把每个邻居作为新的起点递归访问。

循环和递归结合的模式自然出现了：

for (int v : g[u]) {
    if (v == parent) continue; // 避免回到父节点
    depth[v] = depth[u] + 1;  // 更新深度
    dfs(v, u);                 // 递归访问子节点
}

• 循环负责遍历所有分支。

• 递归负责深入每条分支直到末端。

3. 思路总结

如果想像不到这种写法，可以尝试以下方法训练思维：

1. 抽象问题为树/图：先想“每个节点可以去哪些地方”。

2. 找到重复模式：访问子节点的操作是一样的，每次都需要深度+1并访问它的邻居。

3. 想到递归：每次访问子节点的操作和访问当前节点一样，所以递归自然出现。

4. 处理多分支：每个节点可能有多个邻居，用循环遍历。

换句话说，循环解决“多条路”，递归解决“深度遍历同样的操作”。