DFS 和递归有什么关系？

01DFS 就是递归吗？

不是。

02为什么 DFS 很适合递归？

DFS 每进入一个新节点，就需要记住：

• 我是从哪里来的
• 这个节点还有哪些邻居没处理
• 返回后该继续哪里

函数调用栈天然能保存这些状态。

03递归 DFS 的调用栈长什么样？

D 完成后回到 B，B 完成后再回到 A。

04不用递归能写 DFS 吗？

可以，用 std::stack：

std::stack<int> st;
st.push(start);

while (!st.empty()) {
    int u = st.top();
    st.pop();

    if (visited[u]) continue;
    visited[u] = true;

    for (int v : graph[u]) {
        if (!visited[v]) {
            st.push(v);
        }
    }
}

05递归版和栈版访问顺序一定完全一样吗？

不一定。

如果邻居压栈顺序不同，迭代 DFS 的具体访问顺序也会不同，但仍然遵循深度优先思想。

06什么时候要警惕递归太深？

如果图或树非常深，递归层数可能很大，实际调用栈可能耗尽。