Recursive DFS vs Iterative DFS
Write the recursive version unless the depth could overflow the stack, which in Java means roughly ten thousand frames. Keep the iterative version for deep graphs, for long linked lists, and for the interviewer who asks for it directly.
These are the same traversal. The recursive one hides its stack in the call stack, and the iterative one holds the same nodes in an ArrayDeque you manage yourself. Everything that differs follows from where that stack lives: how deep you can go, what you can see while debugging, and how much code you write.
Side by side
| Dimension | Recursive DFS | Iterative DFS |
|---|---|---|
| Where the stack lives | The JVM call stack | A deque on the heap |
| Depth limit | About 10,000 frames, then StackOverflowError | Bounded by heap, millions of nodes |
| Lines of code | Three or four | Eight to twelve |
| Visit order | Natural, left before right | Reversed unless you push right first |
| Post-order | Falls out, work after both calls return | Needs a visited flag or a second stack |
| Debugging | The stack trace is the path | The stack is a variable you can print |
When to pick each
Recursive DFS
- Trees, where the depth is log n for anything balanced and the recursion reads like the definition.
- Post-order work, where each node's answer depends on its children's answers.
- Backtracking, where undoing a choice on the way back up is the whole technique.
Iterative DFS
- A graph that could be a chain of a million nodes, such as a grid flood fill on a long thin island.
- Linked list problems on an input you did not generate, where the length is unbounded.
- Any language or environment with a small stack, and any interview where the follow-up is convert it to iterative.
Pushing the children in the same order you would visit them. A stack reverses whatever goes in, so pushing left then right pops right first and the traversal comes out mirrored. The fix is one line, pushing right before left, and the bug is invisible on a symmetric test tree, which is exactly how it survives into the interview answer.
Questions people ask
How deep can Java recursion actually go?
Around 10,000 to 20,000 frames with default settings, and it depends on how much each frame holds. A method with several local variables runs out sooner than a tight one. The limit is a thread setting rather than a language rule, so you can raise it with -Xss, which is not an answer available inside an interview sandbox.
Is iterative DFS faster?
Slightly, and rarely enough to matter. A method call is cheap, and the heap allocation for an explicit stack is not free either. Choose on depth safety and on which version you can write correctly under pressure, not on speed.
What about iterative post-order?
It needs more bookkeeping than the other two orders, because a node has to be seen twice: once on the way down and once after both subtrees finish. The usual trick avoids that entirely by running a pre-order with the children pushed the other way round, giving root, right, left, and reversing the result at the end.