콜 스택: 재귀가 실제로 사는 곳

"재귀는 마법이 아니야. 앞에서 이미 만난 스택 위에서 돌아가는 것뿐이지. 재귀 호출마다 프레임이 쌓이고, 답은 그 프레임이 풀리면서 되돌아와. 스택이 보이는 순간 재귀는 신비하기를 멈추고 기계적인 것이 돼."

재귀는 콜 스택 위에서 돌아

스택과 큐 트랙에서 콜 스택이 활성 함수 호출마다 하나씩 쌓인 진짜 프레임 더미라는 걸 배웠지. 재귀는 그냥 그 스택이 높이 자라는 거야. 재귀 호출이 일어날 때마다 자기 인자와 지역 변수를 담은 새 프레임이 push되고, 그 프레임은 실행 도중에 멈춘 채로 재귀 자식이 반환하기를 기다려. base case가 마침내 반환하면 프레임이 하나씩 pop되면서 각자 멈췄던 자리에서 재개하고 결과를 결합하지. 내려가는 건 호출이 쌓이는 거고 올라오는 건 스택이 풀리는 거야. 메커니즘은 이게 다야.

깊이가 곧 공간이야

재귀가 메모리를 쓰는 이유가 여기 있어. 복잡도 트랙에서 짚었던 그 지점을 구체적으로 보는 거지. d단계 깊이의 재귀는 프레임 d개를 스택에 동시에 얹어 두니까, 다른 걸 하나도 할당하지 않아도 O(d) 공간을 써. 균형 잡힌 트리라면 깊이가 log n이라 무시해도 되고. 그런데 사슬이거나 깊은 선형 재귀라면 깊이가 n이라 스택도 O(n)이야. n이 크면 스택이 바닥나지. Python은 기본적으로 재귀를 약 1000 프레임으로 제한하고 그걸 넘으면 RecursionError를 던져. 이 제한은 제안이 아니라 안전장치야. 깊은 재귀는 진짜로 죽을 수 있거든.

재귀는 콜 스택 위에서 돌아. 호출마다 자식을 기다리는 프레임이 하나씩 쌓이니까 깊이 d가 곧 O(d) 공간이야. 너무 깊어지면 Python의 약 1000 한계에 걸려 RecursionError가 나고. 재귀 깊이와 스택 공간은 같은 말이야.

Python에는 꼬리 호출 최적화가 없어

어떤 언어는 꼬리 재귀, 그러니까 재귀 호출이 함수가 하는 마지막 일인 경우를 최적화해. 새 프레임을 쌓는 대신 지금 프레임을 재사용해서 깊은 재귀를 O(1) 공간으로 만드는 거지. Python은 일부러 그렇게 하지 않아. Guido van Rossum이 스택 트레이스를 읽기 쉽게 유지하는 쪽을 택했거든. 그래서 Python에서는 n단계 재귀가 진짜로 프레임 n개를 써. 예외 없이. 재귀가 깊어질 수 있는 상황이라면, 거대한 리스트를 처리하거나 한쪽으로 퇴화한 트리를 걷는 경우 같은 거라면, 해법은 명시적 스택을 써서 반복으로 바꾸는 것이야. 스택과 그래프 트랙에서 본 스택과 재귀의 등가성 그대로고. 스택을 힙에 직접 두고 관리하면 콜 스택 한계를 통째로 비껴갈 수 있어.

피파의 고백

긴 리스트를 재귀로 처리하다가 RecursionError를 만났는데, 내 첫 본능은 sys.setrecursionlimit(1000000)이었어. 천장을 올리자! 아빠가 막았지. 그건 메모리를 더 주는 게 아니라 그냥 Python이 더 세게 죽게 만드는 거고, 때로는 인터프리터 전체가 segfault로 날아간다고. 진짜 해법은 재귀를 명시적 스택을 쓰는 반복문으로 다시 쓰는 거였어. 그때 재귀 한계가 대체로 진실을 말한다는 걸 배웠어. 답은 거의 '한계를 올려'가 아니라 거의 언제나 '그렇게 깊이 쌓지 마'야.

Code

재귀 깊이가 곧 스택 프레임, 깊은 재귀는 루프로·python

import sys

# 각 호출이 프레임 추가. 이 재귀는 n 깊이 -> O(n) 스택 공간.
def depth_demo(n):
    if n == 0:
        return 0
    return 1 + depth_demo(n - 1)   # n 프레임이 n-1 프레임을 기다림

print(depth_demo(100))             # 100 — 괜찮아, 100 프레임
print("Python's recursion limit:", sys.getrecursionlimit())   # ~1000

# depth_demo(100000) 은 RecursionError 를 낼 거야 — 프레임 너무 많음.
# 그냥 한계 올리지 마. 네 명시적 스택으로 반복으로 바꿔:
def sum_to_iterative(n):
    total = 0
    stack = list(range(1, n + 1))   # 네 스택은 콜 스택 아니라 힙에 살아
    while stack:
        total += stack.pop()
    return total

print(sum_to_iterative(100000))    # 잘 작동 — 콜-스택 한계 안 걸림
# 재귀 = 콜 스택 쓰기. 명시적 스택 반복 = 네 스택 쓰기.
# 같은 로직, 근데 네 건 메모리 허용하는 만큼 커질 수 있어.

Exercise

재귀 함수가 노드 5만 개짜리 연결 리스트를 노드마다 한 번씩 재귀하며 처리한다고 하자. Python에서 돌리면 무슨 일이 벌어질지 예측하고, 콜 스택 관점에서 왜 그런지 설명해 봐. 그다음 반복 버전으로 어떻게 바꿀지 말해. 어떤 자료구조가 콜 스택을 대신하고, 왜 그게 크래시를 피하게 해 줄까?

Hint

노드가 5만 개면 프레임도 5만 개 쌓이고, Python의 약 1000 한계를 넘어서 RecursionError가 나. 힙에 명시적 스택이나 누산기를 두고 리스트를 걷는 while 반복문으로 바꾸면 돼. 힙은 재귀 한계에 묶이지 않으니까 메모리가 허락하는 깊이까지 확장돼.

재귀는 콜 스택 위에서 돌아

깊이가 곧 공간이야

Python에는 꼬리 호출 최적화가 없어

피파의 고백

Code

External links

Exercise

Progress

댓글 0