How Are DFS and Recursion Related? - Computer Mini Universe

Think together · Start with a little story

Whenever the robot enters a room, it says, “Check the neighbors of this room in the same way.” That sounds like a function calling itself.

Lay out the process

Follow the steps, then explain them in your own words

EnterMark the room
Call recursivelyExplore one neighbor
ReturnGo back to the current room
ContinueTry the next unvisited neighbor

Recursion naturally expresses the downward exploration and return steps of DFS.

Each call remembers the current room and which direction to try next. You can also implement DFS with an explicit stack; recursion is not required.

04Can you write DFS without recursion?

Yes, with std::stack:

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

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

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);
        }
    }
}

Your turn to try

Can you write DFS by managing your own stack without recursion?

Ready? Open to see the explanation

Yes. The key is to preserve depth-first visit order and the state needed to return.

Lay out the process

01Is DFS the same as recursion?

DFS

Recursion

02Why does DFS fit recursion well?

03What does the call stack of recursive DFS look like?

04Can you write DFS without recursion?

05Will recursive and stack-based DFS always visit nodes in the same order?

06When should you watch out for deep recursion?

What have you learned?

Your turn to try

Share Article