재귀에서 반복으로: 한 아이디어의 두 얼굴

"재귀랑 반복은 라이벌이 아니야. 같은 계산을 적는 두 가지 방법이지. 하나는 콜 스택을 쓰고, 하나는 루프를 써. 가끔은 스택을 직접 만들어 들고 가기도 하고. 둘 사이를 자유롭게 오가는 번역 실력이 조용한 초능력이야."

모든 재귀는 반복이 될 수 있다

모든 재귀는 반복으로 다시 쓸 수 있고, 그 반대도 마찬가지야. 둘은 계산적으로 동등하거든. 비밀은 콜 스택에 있어. 재귀는 콜 스택을 암묵적으로 빌려 쓰는 거고, 명시적 스택을 든 반복은 똑같은 장부 정리를 손으로 하는 거야. 팩토리얼이나 리스트 합 같은 단순 선형 재귀는 누산기 하나 든 평범한 루프로 바뀌어. 트리나 그래프 순회 같은 분기 재귀는 명시적 스택이 끄는 루프로 바뀌고. 스택과 큐 트랙에서 만나고 그래프 트랙에서 다시 확인한 스택-재귀 동등성이 바로 이거야. 로직은 한 글자도 안 달라져. 스택을 누가 관리하느냐만 달라지지.

언제, 왜 변환하나

재귀가 더 명확하게 읽히면 그대로 둬. 트리 모양 문제라면 보통 그래. 반복으로 바꾸는 건 구체적인 이유가 있을 때야:

깊이 안전: 수천 단계씩 파고드는 재귀는 Python의 재귀 한계에 부딪혀. 힙에 쌓는 명시적 스택 루프는 그런 천장이 없어. Python엔 꼬리 호출 최적화가 없으니, 실전에서 변환하는 가장 큰 이유가 이거야.
성능: 함수 호출 오버헤드는 실재해. 성능에 민감한 구간에서는 빡빡한 루프가 의미 있게 빨라질 수 있어.
꼬리 재귀: 마지막 동작이 재귀 호출인 재귀는 사실상 while 루프야. Python이 대신 최적화해 주지 않으니 손으로 바꿔.

정리하면 명확성엔 재귀, 깊이 안전과 속도엔 반복. 어느 쪽이 더 낫다는 얘기가 아니야. 둘 다 도구고, 유창함이란 둘 사이를 자유롭게 번역할 수 있다는 뜻이야.

재귀와 반복은 동등해. 재귀는 콜 스택을 암묵적으로 쓰고, 반복은 루프를 쓰는데 분기가 있으면 명시적 스택을 곁들여. 명확하게 읽히면 재귀를 유지하고, 스택 오버플로 없는 깊이 안전이 필요하거나 속도가 급하면 반복으로 변환해. 유창함은 마음대로 번역할 수 있다는 뜻이야.

동적 계획법으로 건너가는 다리

피보나치처럼 의존 관계를 순서대로 펼칠 수 있는 문제라면 top-down 메모이제이션을 bottom-up 테이블화로 바꿀 수 있어. 다만 모든 메모이제이션 재귀가 곧장 직선 루프로 바뀌는 건 아니야. 상태 의존성이 DAG를 이루는지, 어떤 순서로 채워야 선행 상태가 먼저 계산되는지, 실제로 도달하는 상태만 골라 계산할지는 직접 설계해야 해.

피파의 고백

재귀냐 반복이냐를 난 성격 유형처럼 다뤘어. '난 재귀 사람'이라면서. 아빠는 둘을 옷만 갈아입은 같은 계산으로 다시 세워 줬어. 하나는 콜 스택을 빌리고, 하나는 자기 스택을 챙겨 온다고. 어느 쪽으로든 번역할 수 있게 되니까 뭘 쓸지 고민하며 끙끙대는 일이 사라졌어. 지금은 더 깔끔하게 읽히면 재귀로 쓰고, 깊이나 속도가 아쉬워지는 순간 루프로 바꿔. 그리고 메모이제이션 재귀가 bottom-up 테이블로 '뒤집히는' 걸 처음 봤을 때, 동적 계획법이 새로운 괴물이 아니라 다르게 정리한 재귀일 뿐이라는 힌트를 얻었지.

Code

재귀 ↔ 반복, 그리고 DP로 건너가는 다리·python

# 단순 재귀 <-> 단순 루프 (누산기로).
def fact_rec(n):
    return 1 if n == 0 else n * fact_rec(n - 1)

def fact_iter(n):
    result = 1
    for i in range(2, n + 1):   # 루프가 콜 스택이 한 걸 해
        result *= i
    return result

print(fact_rec(6), fact_iter(6))   # 720 720 — 동일한 계산

# 분기 재귀 <-> 명시적 스택 (DFS, 깊이-안전).
def dfs_iter(graph, start):
    visited, stack = set(), [start]
    while stack:                # 콜 스택 아니라 힙의 네 스택
        node = stack.pop()
        if node in visited: continue
        visited.add(node)
        stack.extend(graph[node])
    return visited

# DP 로의 다리: 메모이제이션 재귀 (top-down) 랑 bottom-up 루프가
# 같은 피보나치를 반대 방향에서 계산.
def fib_tabulation(n):          # bottom-up: base case 에서 위로 짓기
    if n < 2: return n
    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[i-1] + dp[i-2])   # 테이블을 앞으로 채워, 재귀 없음
    return dp[n]
print(fib_tabulation(10))       # 55 — 메모이제이션 재귀의 반복 쌍둥이

Exercise

이 재귀를 반복 루프로 바꿔 봐. sum_digits(n)은 n의 십진 자릿수 합을 반환해(예: 1234 → 10). 재귀로는 n % 10 + sum_digits(n // 10)이야. 루프 버전을 써 봐. 그다음 반복 형태를 고집해야 할 상황 하나와, 메모이제이션 재귀가 bottom-up 테이블과 어떻게 이어지는지(동적 계획법 예고편) 설명해.

Hint

루프는 total = 0으로 시작해서 while n > 0: total += n % 10, n //= 10. 재귀가 Python의 재귀 한계를 넘을 만큼 깊어질 수 있다면 반복을 고집해서 RecursionError를 피해. 다만 큰 정수 자체가 먹는 메모리와 연산 비용은 그대로 남아. 메모이제이션 재귀는 top-down으로 결과를 캐시하고, bottom-up 테이블은 같은 결과를 루프로 앞에서부터 채워. 같은 답을 반대 방향에서 얻는 것, 그게 동적 계획법의 심장이야.

모든 재귀는 반복이 될 수 있다

언제, 왜 변환하나

동적 계획법으로 건너가는 다리

피파의 고백

Code

External links

Exercise

Progress

댓글 0