공간 복잡도로 재귀와 반복 구현의 메모리 비용 판단하기

메모리 예산은 알고리즘 설계에서 먼저 드러난다

공간 복잡도는 입력 크기 n에 따라 알고리즘이 요구하는 메모리 사용량의 점근적 상한을 나타낸다. 여기서 입력 자체를 보관하는 공간까지 포함한 총 공간과, 입력 저장 공간을 제외한 보조 공간을 구분해야 한다.

재귀와 반복의 선택은 이 구분을 실제 운영 문제로 끌어온다. 재귀는 호출 깊이가 커질수록 스택 프레임을 쌓고, 반복은 상태를 변수나 명시적 컨테이너로 관리한다. 피크 메모리와 오류 가능성, 확장성은 이 선택에 따라 달라진다.

함수 호출 프레임에는 매개변수, 지역 변수, 반환 주소가 들어간다. 깊이 D의 재귀 호출은 일반적으로 O(D)의 추가 스택 프레임을 사용한다. 반면 힙에는 동적 메모리, 컬렉션, 캐시, 버퍼가 놓이며 수명과 파편화도 함께 관리해야 한다.

꼬리 재귀 최적화(TCO)가 없는 런타임에서는 재귀 깊이 D가 스택 한도를 넘을 때 StackOverflow 또는 RecursionError가 발생한다. TCO 지원 여부만으로 판단해서도 안 된다. 부분 꼬리 재귀, 예외, 디버그 정보는 TCO를 방해할 수 있다.

점근 표기만으로 놓치기 쉬운 비용

분석할 때는 입력 크기 n뿐 아니라 최악·평균·최선 케이스와 데이터 구조의 Footprint(원소당 바이트)를 함께 본다. 프레임과 객체 오버헤드, 정렬과 패딩, 런타임 메타데이터처럼 상수항에 해당하는 요소도 실제 메모리 사용량에는 영향을 준다.

반복 구현은 루프를 중심으로 상태를 명시적 변수나 컨테이너에 옮긴다. 이때 스택 사용량은 O(1) 또는 O(k)로 제한할 수 있다. 명시적 스택이나 큐를 둔다면 재귀 깊이 D와 마찬가지로 O(D)가 될 수도 있지만, 호출 프레임보다 오버헤드가 낮고 상태를 제어하기 쉽다.

정적 분석에서는 점근 표기, 스택 깊이 상한, 자료 구조의 크기를 산정한다. 런타임에서는 피크 메모리, 할당 횟수, 객체 생존 시간을 확인한다. tracemalloc, massif, pprof, jemalloc prof 같은 도구가 이 단계에 쓰인다.

탐색·파싱·DP에서 달라지는 선택

대규모 그래프나 트리를 DFS로 탐색할 때 재귀 구현은 깊은 그래프에서 스택 오버플로 위험을 만든다. 반복과 명시적 스택으로 바꾸면 이 위험을 다루기 쉬워진다. BFS의 큐는 O(V) 메모리를 요구하므로, 메모리 예산에 맞춰 레벨 단위 스트리밍이나 프런티어 압축을 적용한다.

깊게 중첩된 입력을 처리하는 재귀 하향식 파서도 불안정해질 수 있다. 반복형 상태기계(LL(1)/LR) 또는 트램펄린 기법을 고려할 수 있으며, 스트리밍 파싱과 버퍼 재사용은 보조 공간을 줄이는 방법이다.

동적 계획법에서는 Top-down 메모이제이션이 구현을 단순하게 만드는 대신 캐시 사용량을 늘린다. Bottom-up 반복형 구현으로 옮기면 메모리를 O(1)~O(n)으로 축소할 수 있다. 상태가 이전 단계 일부에만 의존한다면 롤링 배열이나 슬라이딩 윈도우를 쓰고, 필요한 경우 비트셋으로 압축한다.

재귀와 반복 구현을 비교하는 기준

항목	재귀	반복
성능	호출 오버헤드 존재, TCO 미지원 시 불리	함수 호출 최소화, 분기 예측 우호
확장성	깊이 D에 따라 스택 선형 증가	O(1) 또는 명시적 컨테이너로 제어 가능
일관성	디버그/옵션에 따라 TCO/프레임 달라짐	런타임/컴파일러 의존도 낮음
안정성	스택 한도 초과 위험	메모리 예산 내 제어, 예측 가능
운영 편의	코드 간결, 가독성 우수	메모리/성능 튜닝 용이, 장기 운영 적합

재귀를 반복으로 바꾸면 프레임 오버헤드 제거에 따라 20~60% 절감을 기대할 수 있다. 함수당 프레임 오버헤드와 호출 깊이에 비례하는 효과다. DP 메모이제이션을 롤링 배열로 바꾸는 경우에는 O(n)에서 O(1)로 축소할 수 있고, 데이터 크기 n이 클수록 수배 절감이 가능하다.

운영 측면에서는 StackOverflow/RecursionError 사건율 0화와 OOM 회피율 증가를 기대할 수 있다. GC 압력 완화로 지연시간 P99가 10~30% 개선된 사례도 관찰된다. 컨테이너나 함수형 서버의 메모리 한도를 맞추기 쉬워지고 HPA 스케일 효율도 높아진다. 프로파일 기준선을 회귀 방지에 쓰면 배포 실패율을 낮추는 데 도움이 된다.

예산을 세우고 구현을 바꾸는 과정

먼저 n의 범위와 분포, 최악 깊이 D를 파악한다. 프로세스 메모리, 컨테이너 limit, 언어 런타임 스택 크기를 기준으로 스택 한도와 메모리 예산을 잡고, 총 공간과 보조 공간을 나눠 상수항까지 산정한다.

꼬리 재귀는 누적자(accumulator)를 도입하고 상태 변수를 드러내는 방식으로 루프로 바꿀 수 있다. 일반 재귀는 호출 인자를 튜플로 스택에 저장해 반복 처리하며, 메모이제이션 기반 DP는 상태 전개 순서를 정의한 뒤 Bottom-up과 롤링 배열 또는 비트셋으로 옮긴다.

변경 뒤에는 피크 RSS, 힙 사용량, alloc/sec를 기준선으로 남긴다. 깊이와 입력 최대값을 대상으로 StackOverflow/RecursionError, OOM 핸들링 경로를 검증하고, 임계 입력 크기와 성능·메모리 예산 상한을 CI 게이트에 고정한다.

메모리 사용량을 검증하는 흐름

⤢✕

Python DFS로 확인하는 호출 스택과 명시적 스택

다음 예시는 Python 3.11+와 Linux/macOS에서 표준 라이브러리 tracemalloc을 사용한다. 큰 트리에서는 재귀 방식이 RecursionError 위험을 가지며, 반복 방식은 명시적 스택을 사용한다.

# python 3.11+
import sys
import tracemalloc

sys.setrecursionlimit(10**6)

# 완전 이진트리 생성 (노드 수 ≈ 2^(h+1)-1)
class Node:
    __slots__ = ("l", "r")
    def __init__(self, l=None, r=None):
        self.l, self.r = l, r

def build_tree(h):
    if h == 0:
        return Node()
    return Node(build_tree(h - 1), build_tree(h - 1))

def dfs_recursive(n: Node):
    if n is None:
        return 0
    return 1 + dfs_recursive(n.l) + dfs_recursive(n.r)

def dfs_iterative(root: Node):
    stack = [root]
    count = 0
    while stack:
        n = stack.pop()
        if n is None:
            continue
        count += 1
        # 자식 push 순서만 다름
        stack.append(n.l)
        stack.append(n.r)
    return count

def measure_peak_bytes(fn, *args):
    tracemalloc.start()
    try:
        result = fn(*args)
        current, peak = tracemalloc.get_traced_memory()
    finally:
        tracemalloc.stop()
    return result, peak  # 바이트

if __name__ == "__main__":
    h = 16  # 높이 16 => 노드 약 131071개
    root = build_tree(h)

    # 재귀 DFS
    try:
        r1, peak1 = measure_peak_bytes(dfs_recursive, root)
        print("recursive count:", r1, "peak bytes:", peak1)
    except RecursionError:
        print("recursive: RecursionError 발생")

    # 반복 DFS
    r2, peak2 = measure_peak_bytes(dfs_iterative, root)
    print("iterative count:", r2, "peak bytes:", peak2)

두 구현은 트리 데이터 구조 자체가 차지하는 메모리는 같다. 차이는 탐색 중 필요한 보조 공간이다. 재귀 방식은 호출 프레임 × 깊이(h)에 비례해 추가 스택을 사용하고, 반복 방식은 파이썬 리스트 스택에 노드 포인터를 저장한다.

실제 수치는 런타임과 GC 타이밍에 따라 다르다. 피크 메모리는 반복 방식이 더 낮거나 유사한 경향을 보인다.