Recursion vs Iteration in Coding Interviews

Anything you can write recursively, you can write iteratively with an explicit stack. Use recursion when the problem is naturally nested, such as trees, backtracking and divide and conquer, because the code stays short. Use iteration when the depth could be large, or memory matters, because recursion spends O(depth) stack space and can hit a limit.

Recursion and iteration compared

	Recursion	Iteration
State lives in	The call stack	Your own variables, or an explicit stack
Time	Usually the same	Usually the same
Extra space	O(depth), always	O(1) for a plain loop, O(depth) with a stack
Reads best for	Trees, backtracking, divide and conquer	Linear scans, level-order work, two pointers
Failure mode	Stack overflow, or the language's recursion limit	Off-by-one errors, more state to track
Backtracking	Automatic: returning undoes the call	Manual: you push and pop the state

Python enforces this with a limit. Its documentation describes the recursion limit as the maximum depth of the interpreter stack, there to stop infinite recursion from overflowing the C stack and crashing Python, and says to raise it only with care. So on a list or a skewed tree with a large depth, a recursive Python solution can fail where a loop would not.

A worked example where both apply

Find the maximum depth of a binary tree. The recursive version says the definition almost word for word. The iterative one does the same work, with the stack made visible.

def max_depth_recursive(node):
    if node is None:
        return 0
    return 1 + max(max_depth_recursive(node.left), max_depth_recursive(node.right))

def max_depth_iterative(root):
    best = 0
    stack = [(root, 1)] if root else []  # the stack the recursion had for free
    while stack:
        node, depth = stack.pop()
        best = max(best, depth)
        if node.left:
            stack.append((node.left, depth + 1))
        if node.right:
            stack.append((node.right, depth + 1))
    return best

Both are O(n) time and O(h) space for height h, so the iterative version does not save memory in the worst case. What it changes is where that memory lives: on the heap, which is much larger than the call stack. A tree that is a straight line of a hundred thousand nodes would stop the recursive version at Python's limit, and the iterative one would finish.

Which to pick in an interview, and how to say why

Trees, backtracking, divide and conquer: recursion, because clarity is the point. Say what the depth is.
A simple loop would do: iteration. Summing a list recursively adds stack space for nothing.
Unknown or adversarial depth: an explicit stack, or a queue for level-order work.
Asked to "remove the recursion": copy the arguments of each call into a tuple on a stack, as above.

What a strong candidate might say

A tree is defined recursively, so I'll write this recursively, since a node's depth is just one plus the larger of its children's. It's O(n) time, and O(h) stack space for height h, which is O(log n) if the tree is balanced and O(n) if it's a straight line. If this input could be very deep, I'd use an explicit stack instead, because the language's recursion limit could stop the recursive version. The time and the worst-case space stay the same.