호출 스택 시각화
Python의 sys 모듈과 출력 추적을 사용해 스택 프레임이 늘어나고 줄어드는 모습을 관찰하고, 깊은 재귀에서 스택 오버플로가 발생할 위험을 이해합니다.
호출 스택 시각화은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
호출 스택이란 무엇인가
Python의 모든 함수 호출은 호출 스택에 스택 프레임을 생성합니다. 프레임에는 함수의 지역 변수, 반환 주소(함수가 반환한 후 실행이 재개되는 위치), 현재 명령 포인터가 저장됩니다. 함수가 반환되면 프레임이 pop되고 제어가 호출자에게 넘어갑니다. 호출할 때마다 호출 스택은 아래 방향으로 커지고, 반환할 때마다 줄어듭니다.
호출 스택을 이해하는 것은 재귀 코드 디버깅, 메모리 사용량 추정, 깊은 재귀에서 발생하는 스택 오버플로 오류 방지에 필수적입니다.
import traceback
def outer():
inner()
def inner():
# Print the current call stack
traceback.print_stack()
outer()
# Shows: module -> outer -> innersys로 스택 프레임 관찰하기
Python의 sys 모듈은 실행 중 호출 스택을 검사하는 도구를 제공합니다. sys._getframe(n)은 현재 함수보다 n단계 위에 있는 스택 프레임을 반환합니다. 각 프레임에는 지역 변수의 f_locals 딕셔너리와 함수 이름을 나타내는 f_code.co_name이 있습니다. 재귀 함수 안에 디버그 출력문을 삽입하면 프레임이 쌓였다가 사라지는 과정을 확인할 수 있습니다.
import sys
def countdown(n):
depth = 0
frame = sys._getframe(0)
while frame:
depth += 1
frame = frame.f_back
print(' ' * (n * 2) + f'countdown({n}) called, stack depth={depth}')
if n <= 0:
return
countdown(n - 1)
print(' ' * (n * 2) + f'countdown({n}) returning')
countdown(3)호출 스택에서 factorial 추적하기
호출 스택에서 factorial(4)를 추적해 보십시오. 호출이 쌓입니다: factorial(4)가 factorial(3)을 호출하고, factorial(3)이 factorial(2)를 호출하고, factorial(2)가 factorial(1)을 호출하고, factorial(1)이 factorial(0)을 호출합니다. 기저 조건에 도달했을 때 스택에는 프레임이 5개 있습니다. 반환이 역순으로 진행됩니다: factorial(0)은 1을 반환하고, factorial(1)은 1×1=1을 반환하고, factorial(2)는 2×1=2를 반환하고, factorial(3)은 3×2=6을 반환하고, factorial(4)는 4×6=24를 반환합니다. 깊이는 n+1이고 공간 복잡도는 O(n)입니다.
def factorial(n, indent=0):
prefix = ' ' * indent
print(prefix + f'-> factorial({n})')
if n == 0:
print(prefix + '<- returns 1')
return 1
result = n * factorial(n - 1, indent + 1)
print(prefix + f'<- returns {result}')
return result
factorial(4)스택 오버플로: Python의 재귀 제한
호출 스택이 제한을 초과하면 Python은 RecursionError를 발생시킵니다(기본값은 약 1000개의 프레임입니다). 이는 무한 재귀가 메모리를 모두 소모하는 것을 방지합니다. 입력 크기 n이 10^4 이상인 문제에서는 제한을 늘리지 않는 한 깊이가 O(n)인 재귀 해답이 충돌합니다. 반복형 대응 구현은 바깥 함수를 위한 프레임 하나만 사용하므로 O(1) 스택 공간을 사용합니다.
import sys
print('Recursion limit:', sys.getrecursionlimit())
def deep_recursion(n):
if n == 0:
return 0
return 1 + deep_recursion(n - 1)
# Safe: within limit
try:
print(deep_recursion(900))
except RecursionError:
print('Overflow at 900')
# Overflow
try:
print(deep_recursion(2000))
except RecursionError:
print('RecursionError at 2000 — limit exceeded!')재귀 제한 늘리기
sys.setrecursionlimit(n)을 사용해 Python의 재귀 제한을 늘릴 수 있지만, 이는 임시방편입니다. 기본 제한이 존재하는 이유는 각 스택 프레임이 메모리를 차지하기 때문입니다(CPython에서는 일반적으로 수백 바이트입니다). 제한을 10^6으로 설정한 뒤 깊이가 10^5인 재귀를 호출하면 수백 메가바이트의 스택 공간이 할당될 수 있습니다. 올바른 해결책은 보통 반복형 해답으로 바꾸거나 메모이제이션을 사용해 깊이를 줄이는 것입니다.
import sys
# Only increase when you are certain of the maximum depth
# and have confirmed it is safe
original = sys.getrecursionlimit()
sys.setrecursionlimit(5000)
def sum_to(n):
if n == 0:
return 0
return n + sum_to(n - 1)
print(sum_to(3000)) # Works with increased limit
sys.setrecursionlimit(original) # restore
print('Limit restored:', sys.getrecursionlimit())상호 재귀에서의 호출 스택
상호 재귀란 함수 A가 함수 B를 호출하고 함수 B가 함수 A를 호출하는 경우입니다. 호출 스택에서는 A와 B의 프레임이 번갈아 나타납니다. 이 패턴은 짝수/홀수 판별과 상태 기계 시뮬레이션에 사용됩니다. 스택 깊이가 제한된 상태로 유지되는 한 올바르게 작동하지만, 단순한 선형 재귀보다 깊이를 추론하기 어려울 수 있습니다.
def is_even(n):
if n == 0:
return True
return is_odd(n - 1)
def is_odd(n):
if n == 0:
return False
return is_even(n - 1)
# Stack alternates: is_even(4)->is_odd(3)->is_even(2)->is_odd(1)->is_even(0)
print(is_even(4)) # True
print(is_odd(5)) # True
print(is_even(7)) # False꼬리 호출과 Python이 이를 최적화하지 않는 이유
꼬리 호출은 반환하기 전에 수행할 계산이 없는, 즉 반환 직전의 마지막 연산인 재귀 호출입니다. Haskell이나 Scheme과 같은 언어에서는 꼬리 호출을 반복문으로 최적화합니다(꼬리 호출 최적화, TCO). 그러면 O(1) 스택 공간을 사용할 수 있습니다. Python이 TCO를 의도적으로 구현하지 않는 이유는 Guido van Rossum이 설명했듯이, 공간 절약보다 디버깅을 위해 전체 스택 추적을 보존하는 것이 더 중요하다고 판단했기 때문입니다. 따라서 Python에서 꼬리 재귀 코드는 여전히 O(n) 스택 공간을 사용합니다.
# Tail-recursive factorial (accumulator pattern)
def factorial_tail(n, acc=1):
if n == 0:
return acc
return factorial_tail(n - 1, acc * n) # tail call
# In Python, this still uses O(n) stack space (no TCO)
# But it IS semantically tail-recursive
print(factorial_tail(6)) # 720
print(factorial_tail(10)) # 3628800
# Iterative version: same logic, O(1) stack
def factorial_iter(n):
acc = 1
while n > 0:
acc *= n
n -= 1
return acc
print(factorial_iter(10)) # 3628800재귀 트리 출력하기
재귀 트리를 시각화하면 중복 하위 문제가 발생하는 위치(메모이제이션의 대상)를 파악하는 데 도움이 됩니다. 트리를 출력하는 간단한 방법은 레벨마다 공백 2칸씩 늘어나는 indent 매개변수를 추가하는 것입니다. 각 호출은 진입할 때 인수를 출력하고, 종료할 때 반환 값을 출력합니다. 이를 피보나치(5)에 실행하면 지수적으로 분기하고 호출이 반복되는 모습을 명확하게 확인할 수 있습니다.
def fib_traced(n, indent=0):
prefix = ' ' * indent
print(prefix + f'fib({n})')
if n <= 1:
print(prefix + f'=> {n}')
return n
result = fib_traced(n-1, indent+1) + fib_traced(n-2, indent+1)
print(prefix + f'=> {result}')
return result
fib_traced(4)
# Shows the branching tree with duplicated sub-problems스택 깊이 = 공간 복잡도
어떤 재귀 함수에서든 최대 호출 스택 깊이는 실행 중 어느 시점에서든 최대 재귀 깊이와 같습니다. 이 깊이는 보조 공간 복잡도와 직접적으로 같습니다. 선형 재귀(팩토리얼, 피보나치, 문자열 뒤집기)의 깊이는 O(n)입니다. 분할 정복 알고리즘(병합 정렬, 이진 탐색)의 깊이는 O(log n)입니다. 트리 순회의 깊이는 O(h)이며, 여기서 h는 트리의 높이입니다(균형 잡힌 경우 O(log n), 최악의 경우 O(n)).
# Recursion depth = space complexity
# Linear recursion: O(n) stack
def linear_depth(n):
if n == 0: return 0
return 1 + linear_depth(n - 1) # depth = n
# Logarithmic recursion: O(log n) stack
def log_depth(n):
if n <= 1: return 0
return 1 + log_depth(n // 2) # depth = log2(n)
print('n=32 linear depth:', 32)
print('n=32 log depth:', log_depth(32)) # 5
print('n=1024 log depth:', log_depth(1024)) # 10명시적 스택으로 재귀를 반복으로 바꾸기
모든 재귀 알고리즘은 Python 목록을 사용해 호출 스택을 명시적으로 관리함으로써 반복형으로 만들 수 있습니다. OS가 프레임을 관리하도록 두는 대신 목록에 ‘작업’을 넣고 루프에서 pop합니다. 이렇게 하면 Python의 재귀 제한을 없애고 프레임당 오버헤드를 줄일 수 있지만, 코드가 더 복잡해집니다. 앞서 살펴본 명시적 스택을 사용하는 반복형 DFS는 정확히 이 패턴을 따릅니다.
# Recursive inorder traversal -> iterative with explicit stack
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder_iterative(root):
result = []
stack = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
result.append(curr.val)
curr = curr.right
return result
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6))
print(inorder_iterative(root)) # [1, 2, 3, 4, 6]요약: 호출 스택과 공간
호출 스택은 모든 재귀의 배경에서 작동하는 숨은 자료 구조입니다. 호출 스택의 깊이는 재귀 알고리즘의 공간 복잡도와 같습니다. Python은 이를 약 1000으로 제한하므로 O(n) 재귀 깊이를 가진 알고리즘에는 제한을 늘리거나(위험) 반복형으로 다시 작성하는 방법이 필요합니다. 면접에서 재귀 코드를 작성할 때는 호출 스택으로 인한 공간 복잡도를 항상 명시하십시오. ‘이 코드는 재귀 깊이에 O(n) 공간을 사용합니다’ 또는 ‘균형 트리 순회에는 O(log n) 공간을 사용합니다’라고 말하면 됩니다.
빠른 확인
이 단원에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인하십시오.
단원 복습
이 단원에서 배운 내용: 각 재귀 호출은 지역 변수와 반환 주소를 담은 스택 프레임을 생성합니다, 최대 스택 깊이는 재귀의 보조 공간 복잡도와 같습니다, Python의 재귀 제한(약 1000) 때문에 깊이가 O(n)인 알고리즘은 큰 n에서 위험하므로 명시적 스택을 사용해 반복형으로 바꾸십시오. 다음으로 재귀 해답과 반복 해답을 비교하고 각각 언제 사용할지 알아봅니다.
자주 묻는 질문
“호출 스택 시각화” 강의는 무료인가요?
네 — “호출 스택 시각화” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“호출 스택 시각화”에서 뭘 배우나요?
Python의 sys 모듈과 출력 추적을 사용해 스택 프레임이 늘어나고 줄어드는 모습을 관찰하고, 깊은 재귀에서 스택 오버플로가 발생할 위험을 이해합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“호출 스택 시각화” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.