iteration과 recursion — 트레이드오프는 무엇인가요?

Question

Accepted Answer

**Iteration(반복)**은 루프를 사용하고, **recursion(재귀)**은 자기 호출을 사용합니다. 둘은 동등하게 강력하지만(하나로 할 수 있는 모든 것은 다른 하나로도 가능) 명료성과 비용 면에서 차이가 있습니다.

## 나란히 비교

```python
# 반복적 합계: 상수 추가 공간
def sum_iter(n):
    total = 0
    for i in range(1, n + 1):
        total += i        # 루프에서 누적
    return total

# 재귀적 합계: call stack 사용
def sum_rec(n):
    if n == 0:
        return 0
    return n + sum_rec(n - 1)
```

## 비교

| 측면 | Iteration | Recursion |
|--------|-----------|-----------|
| 메모리 | O(1) 추가 | O(깊이) 스택 |
| 가독성 | 선형 작업에 좋음 | 트리 / 분할 정복에 좋음 |
| 위험 | 무한 루프 | 스택 오버플로 |
| 속도 | 보통 더 빠름(호출 오버헤드 없음) | 프레임당 호출 오버헤드 |

## 어느 것을 언제 사용하나

- 단순한 선형 순회와 스택 깊이가 커질 수 있을 때는 **iteration**을 사용하세요.
- 문제가 자연스럽게 재귀적이고(트리, 그래프, backtracking) 깊이가 제한적일 때는 **recursion**을 사용하세요.

## 함정

깊은 재귀는 스택 오버플로 위험이 있습니다. 깊이가 제한이 없을 때는 핫한 재귀 코드를 (보통 명시적 스택으로) 반복으로 변환하세요.

## 왜 중요한가

올바른 스타일을 선택하면 코드를 정확하면서도 읽기 쉽게 유지할 수 있습니다.

Recursion은 트리와 그래프 코드를 우아하게 만들지만, 그 메모리 비용을 알면 깊은 입력에서 크래시를 피할 수 있습니다.

이 트레이드오프 판단은 면접관이 "이것을 반복으로 변환해 보세요"라고 요청할 때 정확히 살펴보는 부분입니다.

측면	Iteration	Recursion
메모리	O(1) 추가	O(깊이) 스택
가독성	선형 작업에 좋음	트리 / 분할 정복에 좋음
위험	무한 루프	스택 오버플로
속도	보통 더 빠름(호출 오버헤드 없음)	프레임당 호출 오버헤드

나란히 비교

question.related

비교

어느 것을 언제 사용하나

함정

왜 중요한가