Recursion versus iteration
“When is recursion the right tool, when is iteration better, and what does recursion cost?”
What this tests
- Whether the candidate understands that recursion is iteration with an implicit stack.
- Awareness of stack depth limits and when they actually bite.
- Ability to identify problems whose structure is naturally recursive (trees, backtracking, divide and conquer).
- Knowing how to convert recursion to iteration when necessary.
Strong answer
Recursion is the right tool when the problem is defined in terms of smaller copies of itself and there is state to remember on the way back up: tree traversals, Divide and Conquer, backtracking over choices, and DFS where you undo a choice after exploring it. In those cases the call stack is doing real work — holding the path — and an iterative version would need an explicit stack that mirrors it exactly.
Iteration is better when the recursion is linear (one recursive call, nothing done after it — tail-recursive), because then the stack holds nothing useful and the depth is pure cost. A linked list walk, a linear DP, and a binary search should be loops. The cost of recursion is O(depth) stack memory and a real risk of stack overflow: Python defaults to about 1000 frames, and a DFS over a 10^5-node path graph will crash.
A strong candidate knows the conversion: replace the call stack with an explicit Stack holding the same frame data, and turn top-down Memoization (Top-Down DP) into bottom-up Tabulation (Bottom-Up DP) when depth is the problem. They also note that iterative code is easier to instrument and debug but recursive code is often shorter and closer to the proof of correctness.
Green flags · Red flags
- Says recursion is an implicit stack and explains what the frames store.
- Gives a concrete depth limit and a concrete crash scenario (deep DFS, linked list recursion).
- Distinguishes linear from branching recursion.
- Knows memoization vs tabulation as the recursive vs iterative faces of DP.
- Thinks recursion is "slower" without saying why, or "always fine".
- Cannot convert a simple recursive traversal to an explicit stack.
- Unaware of stack depth limits.
Follow-up questions
Each follow-up changes a requirement; the right answer changes with it.