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

"재귀랑 반복은 라이벌이 아니야 — 같은 계산을 쓰는 두 방법이야. 하나는 콜 스택을 쓰고; 다른 하나는 루프 (그리고 가끔 네 스택) 를 써. 둘 사이를 번역하는 법을 아는 게 조용한 초능력이야."

재귀인 건 다 반복이 될 수 있다

모든 재귀가 반복으로 다시 쓰일 수 있고, 반대도 — 계산적으로 동등해. 이유는 콜 스택이야: 재귀가 암시적으로 쓰고, 명시적 스택 있는 반복이 똑같은 장부 관리를 손으로 해. 단순 선형 재귀 (팩토리얼, 리스트 합) 는 누산기 있는 평범한 루프로 변환돼. 분기 재귀 (트리랑 그래프 순회) 는 명시적 스택으로 구동되는 루프로 — 정확히 Stacks 랑 Graphs 트랙에서 만난 스택-대-재귀 동등성. 로직이 동일; 누가 스택을 관리하냐만 바뀌어.

언제 (그리고 왜) 변환하나

재귀가 더 명확히 읽히면 — 트리 모양 문제엔 보통 그래 — 유지해. 구체적 이유 있을 때 반복으로 변환:

깊이 안전: 수천 깊이 갈 수 있는 재귀는 Python 재귀 한계를 쳐; 힙의 명시적-스택 루프는 안 그래. (Python 의 가장 큰 이유, 꼬리 호출 최적화 없으니.)
성능: 함수-호출 오버헤드가 진짜야; 빡빡한 루프가 hot path 에서 의미 있게 빠를 수 있어.
꼬리 재귀: 마지막 행동이 재귀 호출인 재귀는 자명하게 while 루프 — Python 이 최적화 안 해주니, 손으로 해.

판단: 명확성엔 재귀, 깊이-안전이랑 속도엔 반복. 어느 것도 '더 나음' 이 아니라 — 도구고, 유창함은 둘 사이를 자유롭게 번역하는 거야.

재귀랑 반복은 동등해 — 재귀가 콜 스택을 암시적으로, 반복이 루프 (분기 케이스엔 명시적 스택) 를 써. 명확성엔 재귀 유지; 깊이-안전 (스택 오버플로 없음) 이나 속도엔 반복으로 변환. 유창함은 마음대로 번역하는 거야.

동적 계획법으로의 다리

다음 트랙을 여는 변환이야. 피보나치 재앙 떠올려: 재귀 + 캐시 (메모이제이션) 가 O(2ⁿ) 를 O(n) 으로 무너뜨렸어 — 그게 top-down DP, 기억하는 재귀. 이제 뒤집어: 내려가며 캐시하는 대신, base case 에서 위로 루프로 답을 지어, 테이블을 채워. 그게 bottom-up 테이블화 (tabulation) — 메모이제이션 재귀의 반복 쌍둥이. 메모이제이션 재귀랑 테이블화가 반대 방향에서 같은 걸 계산하고, 캐시-있는-재귀가 bottom-up 루프가 될 수 있다는 인식이 동적 계획법, 바로 다음 트랙으로의 문이야.

피파의 고백

난 재귀랑 반복을 성격 선택처럼 다뤘어 — '난 재귀 사람.' 아빠가 다른 옷 입은 같은 계산으로 재구성했어: 하나는 콜 스택을 빌리고, 하나는 자기 걸 가져와. 어느 쪽이든 번역할 수 있게 되니, 뭘 쓸지 고뇌하길 멈췄어 — 더 깔끔히 읽히면 재귀를 쓰고 깊이나 속도가 요구하는 순간 루프로 변환해. 그리고 메모이제이션 재귀가 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 테이블이랑 어떻게 관계되는지 (DP 예고) 설명해.

Hint

루프: total = 0; while n > 0: total += n % 10; n //= 10. 깊은-재귀 변종에서 n 이 천문학적으로 클 수 있으면 반복을 고집해 (RecursionError 피하려). 메모이제이션 재귀는 top-down 결과를 캐시; bottom-up 테이블이 같은 결과를 루프로 앞으로 채워 — 같은 답, 반대 방향, 그게 동적 계획법의 심장.

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

재귀인 건 다 반복이 될 수 있다

언제 (그리고 왜) 변환하나

동적 계획법으로의 다리

피파의 고백

Code

External links

Exercise

Progress

댓글 0