An engineer wants to convert a deep recursive algorithm to an iterative one using an explicit stack because production traffic is hitting stack-overflow crashes. What does that conversion actually buy you, and where do people get it wrong?

technical-conceptual · Senior level · software-engineering

What the interviewer is really asking

Assesses understanding of how an explicit stack replaces the call stack to trade limited stack memory for heap memory, the subtlety of preserving execution state across the conversion, and when the conversion is the right fix versus addressing the depth itself.

What to say

• Name what it buys: the call stack is a small fixed-size region, so deep recursion overflows it; an explicit stack on the heap can grow much larger and is bounded by available heap, plus you can fail gracefully with an error instead of a hard crash.
• Flag the hard part: you must reify everything the call frame held — local variables, which child you were processing, and the return point — so for multi-recursive functions (e.g. tree post-order) you push state markers or visited flags, not just nodes, or you'll re-process or skip work.
• Weigh alternatives first: sometimes the real fix is reducing depth (tail-call refactor where supported, an explicitly iterative formulation, or batching/streaming so you don't recurse per element) rather than just relocating the stack — relocation still uses memory, just elsewhere.

What to avoid

• Treating the conversion as a mechanical 'just use a stack' without preserving per-frame state, which silently re-visits or skips nodes for non-tail recursion.
• Claiming it removes the memory cost — it moves the stack from the call-stack region to the heap; deeply recursive work still consumes memory.
• Ignoring simpler fixes like reducing recursion depth or restructuring the algorithm before reaching for a hand-rolled stack.

Example answers

Strong: The win is memory location and graceful failure: the call stack is a small fixed region, so deep recursion blows it, whereas an explicit stack lives on the heap and can grow far larger — and I can check its size and return an error instead of crashing. The trap is state: a call frame holds locals, the child being processed, and where to resume, so for something like post-order traversal I have to push markers or a visited flag, not just nodes, or I'll double-process. Before doing the conversion I'd ask whether I can cut the depth itself — tail-call style or a genuinely iterative formulation — since the conversion relocates memory rather than removing it.

Weak: I'd swap the recursion for a while loop with a stack — push the nodes, pop them, process each one. That gets rid of the stack overflow because we're not recursing anymore.