Iteration vs recursion — what are the trade-offs?

Question

Accepted Answer

**Iteration** uses loops; **recursion** uses self-calls. They are equally powerful (anything you can do with one you can do with the other), but they differ in clarity and cost.

## Side by side

```python
# Iterative sum: constant extra space
def sum_iter(n):
    total = 0
    for i in range(1, n + 1):
        total += i        # accumulate in a loop
    return total

# Recursive sum: uses the call stack
def sum_rec(n):
    if n == 0:
        return 0
    return n + sum_rec(n - 1)
```

## Comparison

| Aspect | Iteration | Recursion |
|--------|-----------|-----------|
| Memory | O(1) extra | O(depth) stack |
| Readability | great for linear work | great for trees / divide-and-conquer |
| Risk | infinite loop | stack overflow |
| Speed | usually faster (no call overhead) | call overhead per frame |

## When to use which

- Use **iteration** for simple linear traversals and when stack depth could be large.
- Use **recursion** when the problem is naturally recursive (trees, graphs, backtracking) and depth is bounded.

## Pitfalls

Deep recursion risks stack overflow; convert hot recursive code to iteration (often with an explicit stack) when depth is unbounded.

## Why it matters

Choosing the right style keeps code both correct and readable.

Recursion makes tree and graph code elegant, but knowing its memory cost lets you avoid crashes on deep inputs.

This trade-off judgment is exactly what interviewers probe when they ask you to "convert this to iterative."

Aspect	Iteration	Recursion
Memory	O(1) extra	O(depth) stack
Readability	great for linear work	great for trees / divide-and-conquer
Risk	infinite loop	stack overflow
Speed	usually faster (no call overhead)	call overhead per frame