iteration と recursion の trade-off は何ですか？

Question

Accepted Answer

**Iteration** は loop を使い、**recursion** は self-call を使います。表現できる力は同じですが、clarity と 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        # loop で accumulate
    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 | linear work に強い | trees / divide-and-conquer に強い |
| Risk | infinite loop | stack overflow |
| Speed | usually faster | call overhead per frame |

## どちらを使うか

- simple linear traversal や stack depth が大きくなり得る場合は **iteration**。
- trees、graphs、backtracking のように problem が naturally recursive で depth が bounded なら **recursion**。

## pitfalls

深い recursion は stack overflow の risk があります。depth が unbounded な hot recursive code は、explicit stack を使った iteration に変換します。

## なぜ重要なのか

right style を選ぶと code は correct で readable になります。recursion は tree/graph code を elegant にしますが、memory cost を理解していないと deep input で crash します。この trade-off judgment は interview でもよく問われます。

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