Iterative vs Recursive DFS — When Each Wins, and How to Convert Between Them

Recursive DFS is prettier. Iterative DFS is safer. Which one wins in an interview depends on the depth of the input, the language's recursion limit, and whether the state you're carrying naturally lives in function arguments or in an explicit stack. This post is the tie-breaker: when the pretty version is fine, when you need the safe version, and how to convert between them without introducing bugs.

The verdict

Recursive DFS. Shorter code, natural fit for tree problems and "state carried along the recursion" (LC 133 Clone Graph, tree height, path sums). Cost: O(depth) call-stack space, plus a real stack-overflow risk in Python (default limit ~1000) and on very deep graphs in any language.

Iterative DFS. Explicit stack of nodes (or (node, state) tuples). Same time complexity, same asymptotic space, but no language-imposed depth limit. Slightly longer to write, safer under adversarial inputs.

Same algorithm. Same visit order (if you push neighbours in reverse to match recursion order). The choice is whether the depth is bounded by the language's ability to recurse.

When to reach for recursive DFS

• Balanced trees. Depth is O(log n). Recursion is safe and the code is half the length.
• Backtracking. The choose/undo rhythm reads naturally as function-return semantics. See the backtracking template post.
• State that naturally lives in function args. LC 104 (max depth), LC 226 (invert tree), LC 236 (LCA). Passing depth, current_path, or accumulator as parameters is cleaner than packing them into stack tuples.
• Small n. Under a thousand nodes in Python; well under a million in Java or C++. Recursion overhead is negligible.
• Post-order semantics. "Do X when I return from the subtree" — natural in recursion, awkward in an iterative stack that needs a visited-state marker per node.

When to reach for iterative DFS

• Adversarial or unknown depth. LeetCode's grid problems (LC 200, LC 79) can have snakes of length m × n. In Python, a 10⁴-cell snake blows the recursion limit.
• Very large n. Anywhere n > 10⁴ or so in Python. sys.setrecursionlimit(10**6) also works, but the iterative habit is portable across languages that don't offer that escape hatch.
• Interview requirement. Some interviewers explicitly ask for "no recursion" — a solved case, not a debate.
• Explicit state on the stack. When you need to modify or inspect the stack contents mid-traversal (LC 155 Min Stack, some monotonic-stack patterns) the iterative form is natural and the recursive form is contorted.
• Post-order in a specific iterative style. When you need reverse-post-order on a graph (topological sort's "emit-on-finish" variant), a hand-rolled iterative traversal with a "colour" marker per node is the interview-classic solution.

Side by side

Worked example — recursive (LC 104 Maximum Depth of Binary Tree)

Return the maximum depth of a binary tree.

Balanced or not, LeetCode's tree problems have depth well under recursion limits. Recursive is five lines and reads exactly like the problem statement.

def maxDepth(root):
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

The iterative version needs a stack of (node, depth) tuples and a running maximum — twice the code, no material benefit.

Worked example — iterative (grid DFS on a huge board)

Count connected components on a large grid where the longest snake could reach m × n cells.

Recursive DFS in Python hits RecursionError on adversarial inputs. Iterative DFS uses a manual stack and scales to any input size.

def numIslands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    for r0 in range(rows):
        for c0 in range(cols):
            if grid[r0][c0] != '1':
                continue
            # Iterative DFS from (r0, c0).
            stack = [(r0, c0)]
            grid[r0][c0] = '0'
            while stack:
                r, c = stack.pop()
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                        grid[nr][nc] = '0'    # mark on push, not on pop
                        stack.append((nr, nc))
            count += 1

    return count

Same visit order as recursive DFS on a grid, no recursion-limit worry.

Converting between them

To port recursive DFS to iterative:

1. Replace the recursive call with stack.append(...).
2. Replace the function's local state with either function parameters (already the case) or a tuple on the stack.
3. Mark visited on push, not on pop. Marking on pop can push the same node many times before any of them process.
4. If neighbour order matters, reverse the neighbour list before pushing — iterative DFS visits in reverse of push order.

To port iterative DFS to recursive: the reverse. Bump sys.setrecursionlimit in Python if you're worried about depth, and expect one line of code per two lines of the iterative form.

Bottom line

Ask: is the recursion depth bounded by something safe?

• Yes, and the state carries naturally along recursion — recursive DFS. Shorter, clearer, no cost.
• No, or the input could be adversarial, or the interviewer asked for no recursion — iterative DFS. Marginally more code, no depth cliff.

The BFS vs DFS post covers when neither DFS style is the right tool (shortest-path in unweighted graphs → BFS; weighted → Dijkstra). This post is only about how to write DFS once you've decided it's DFS.

For the O(depth) auxiliary-space claim on the recursive form, see the space complexity post.