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

"재귀는 마법이 아니야 — 네가 이미 만난 스택 위에서 돌아. 모든 재귀 호출이 프레임을 쌓고; 답은 그 프레임이 풀리며 돌아와. 스택을 보면, 재귀가 신비롭길 멈추고 기계적이 돼."

재귀는 콜 스택 위에서 돈다

Stacks 트랙에서, 콜 스택이 활성 함수 호출당 하나씩, 프레임의 진짜 스택이란 걸 배웠어. 재귀는 그냥 그 스택이 높이 자라는 거야: 각 재귀 호출이 자기 인자랑 지역 변수를 든 새 프레임을 push 하고, 그 프레임이 — 실행 중간에 멈춰 — 재귀 자식이 반환할 때까지 기다려. base case 가 마침내 반환하면, 프레임이 하나씩 pop 돼, 각자 떠난 데서 재개하고 결과를 결합. '내려가기' 는 호출이 쌓이는 거; '올라오기' 는 스택이 풀리는 거. 그게 메커니즘 전부야.

깊이가 공간이다

그래서 재귀가 메모리를 쓰는 거야, Complexity 트랙의 그 점을 구체화한 거: 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 프레임을 써, 끝. 잠재적으로 깊은 재귀가 있으면 (거대 리스트 처리, 퇴화 트리 걷기), 고침은 명시적 스택으로 반복으로 바꾸기 — 정확히 Stacks 랑 Graphs 트랙의 스택/재귀 동등성. 힙에 네 스택을 관리해, 콜-스택 한계를 통째로 피해.

피파의 고백

긴 리스트를 재귀로 처리하다 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