DFS: iterative vs recursive — when should you use each?

Recursive DFS is usually easier to write and easier to read.

Iterative DFS uses your own explicit stack. It is better when the graph or tree may be very deep, when recursion depth is risky, or when you want more control over traversal state.

DFS is naturally recursive because each node says: “visit me, then visit my children or neighbors.”

void dfs(Node node) {
    if (node == null) {
        return;
    }

    visit(node);

    for (Node neighbor : node.neighbors) {
        dfs(neighbor);
    }
}

This is beautiful. But every recursive call adds another frame to the call stack.

Recursive DFS is great when the depth is reasonable and the recursive structure makes the solution easier to understand.

void dfs(Node node, Set<Node> visited) {
    if (node == null || visited.contains(node)) {
        return;
    }

    visited.add(node);
    visit(node);

    for (Node neighbor : node.neighbors) {
        dfs(neighbor, visited);
    }
}

This is often perfect for interview problems like trees, islands, connected components, and backtracking.

Iterative DFS replaces recursive calls with an explicit stack.

void dfsIterative(Node start) {
    Deque<Node> stack = new ArrayDeque<>();
    Set<Node> visited = new HashSet<>();

    stack.push(start);

    while (!stack.isEmpty()) {
        Node node = stack.pop();

        if (visited.contains(node)) {
            continue;
        }

        visited.add(node);
        visit(node);

        for (Node neighbor : node.neighbors) {
            if (!visited.contains(neighbor)) {
                stack.push(neighbor);
            }
        }
    }
}

In Java, prefer Deque with ArrayDeque for stack-style operations instead of the older Stack class.

• The tree or graph depth is small or controlled.
• The recursive structure makes the code much clearer.
• You are doing backtracking.
• You need pre-order, in-order, or post-order tree traversal.
• The interview favors clarity over production hardening.

Iterative DFS becomes important when recursion depth may be too large.

• A graph can have hundreds of thousands of nodes in one chain.
• A tree is extremely skewed, like a linked list.
• The input comes from users or external data and depth is unknown.
• You are writing production code that must avoid stack overflow.
• You need custom control over traversal state.

Imagine a graph that is basically one long chain:

1 -> 2 -> 3 -> 4 -> 5 -> ... -> 1,000,000

Recursive DFS would create one method call per node before it can unwind.

Iterative DFS may visit nodes in a different order than recursive DFS unless you push neighbors carefully.

Recursive DFS visits neighbors in the order of the loop:

for (Node neighbor : node.neighbors) {
    dfs(neighbor);
}

But iterative DFS uses a stack, so the last pushed neighbor is processed first.

// To mimic recursive order,
// push neighbors in reverse order.
List<Node> neighbors = node.neighbors;

for (int i = neighbors.size() - 1; i >= 0; i--) {
    stack.push(neighbors.get(i));
}

For backtracking problems, recursion is often much easier because the call stack naturally remembers where you are.

path.add(choice);

dfs(nextState);

path.remove(path.size() - 1);

You can implement backtracking iteratively, but the code usually becomes more complex because you must manually store extra state.

Recursive DFS is elegant, but some real-world systems can easily exceed safe recursion depth.