A strong answer
They are equally powerful, so the choice is about clarity, safety and cost.
I choose recursion when the problem or the data is recursive: trees, nested structures, divide-and-conquer algorithms such as merge sort, and backtracking searches. The code mirrors the definition, and correctness follows from reasoning about one level at a time. It is safe when the depth is bounded and small, for example logarithmic in a balanced tree.
I choose iteration when the recursion would be a simple chain, such as walking a list or summing numbers, because a loop is equally clear and uses O(1) space; when the depth depends on the input and could be large, since the call stack is only a few megabytes and overflows at depths in the thousands to tens of thousands; and in hot code paths with tiny functions, where call overhead matters, especially in interpreted languages.
Converting is mechanical. A tail-recursive function becomes a loop: parameters become loop variables and the tail call becomes an update. Most languages I'd use, including Python and Java, don't eliminate tail calls, so this matters. General recursion becomes a loop over an explicit stack that holds the pending work; when work must happen after the children, as in a post-order traversal, the stack stores a stage or a marker with each item. A hybrid also works: quick sort recurses into the smaller partition and loops on the larger one, bounding its depth at O(log n).
What the interviewer is listening for
- A clear rule for each choice, with stack depth as the deciding risk.
- Both conversions, including what the explicit stack must remember.
- Awareness of language specifics such as tail-call support and Python's recursion limit.
Common mistakes
- Claiming recursion is always slower or always clearer.
- Assuming tail calls are optimized in Python, Java or JavaScript.
- Forgetting that recursion uses stack space proportional to its depth.