algo · 19

재귀 vs 반복

스택반복재귀

재귀(recursion)는 함수가 자기 자신을 호출해 문제를 더 작은 같은 문제로 풀어 가는 방식이고, 반복(iteration)은 반복문으로 같은 일을 되풀이하는 방식입니다. 둘 다 같은 계산을 표현할 수 있지만 컴퓨터 안에서 쓰는 자원이 다릅니다. 재귀는 호출마다 호출 스택에 프레임을 쌓고, 반복은 변수 몇 개만 갱신합니다.

그래서 재귀는 깊어지면 스택 오버플로우의 위험이 있고, 부분 문제가 겹치는 문제(피보나치)에서는 같은 계산을 지수적으로 되풀이할 수 있습니다. 이 토픽에서는 호출 스택이 쌓이고 풀리는 모습, 피보나치의 중복 계산, 꼬리 재귀가 최적화 지원 여부에 따라 스택을 쓰는 방식을 직접 확인합니다.

핵심 개념

기저 사례와 재귀 단계

재귀는 더 호출하지 않고 답을 돌려주는 기저 사례와, 더 작은 입력으로 자신을 호출하는 재귀 단계로 이루어집니다. 기저 사례가 없으면 끝나지 않습니다.

핵심 개념

호출 스택 프레임

함수를 호출할 때마다 보통 매개변수와 지역 변수, 돌아갈 위치를 담은 프레임이 스택에 쌓이고, 반환하면 꺼내집니다. 재귀 깊이만큼 프레임이 쌓입니다.

핵심 개념

스택 오버플로우

호출 스택은 크기가 한정되어 있습니다. 재귀가 너무 깊어지거나 기저 사례가 없으면 스택이 가득 차 오류가 납니다.

핵심 개념

중복 계산

fib(n)이 fib(n - 1)과 fib(n - 2)를 각각 호출하면 같은 부분 문제를 여러 번 풉니다. 호출 수가 지수적으로 늘어납니다.

핵심 개념

꼬리 호출 최적화

재귀 호출이 함수의 마지막 연산이면 이전 프레임을 재사용해 스택 증가 없이 실행할 수 있습니다. 지원하는 언어와 그렇지 않은 언어가 있습니다.

핵심 개념

반복과 명시적 스택

깊이가 큰 입력은 반복문으로 바꾸거나, 호출 스택 대신 직접 만든 스택 자료구조에 상태를 쌓아 같은 일을 합니다.

공간이 다릅니다 — 재귀는 깊이에 비례하는 O(깊이)의 스택 공간을 쓰고, 같은 계산의 반복문은 보통 변수 몇 개의 O(1)입니다. 팩토리얼 fact(n)은 재귀에서 프레임이 n개 쌓입니다.

시간은 알고리즘이 정합니다 — 재귀냐 반복이냐보다 같은 계산을 몇 번 하는지가 중요합니다. 중복을 없애지 않은 재귀 피보나치는 지수 시간, 값을 저장하거나 반복으로 바꾸면 덧셈을 상수 시간으로 볼 때 n에 비례합니다.

재귀가 자연스러운 문제가 있습니다 — 트리 순회, 분할정복, 백트래킹처럼 구조 자체가 재귀적인 문제는 재귀로 쓰면 코드가 짧고 의도가 드러납니다.

깊이 한도를 확인하세요 — CPython은 재귀 깊이의 기본 한도가 1000이고 자바는 스택 크기에 따라 StackOverflowError가 납니다. 입력이 크면 반복이나 명시적 스택이 안전합니다.

이 시각화에서 확인할 것 — "호출 스택" 탭에서 fact(5)의 프레임이 5개까지 쌓이고 하나씩 반환되는 모습과 반복문의 변수 두 개를, "중복 계산" 탭에서 fib(5)의 호출 15번 중 주황색 중복 호출을, "꼬리 호출" 탭에서 최적화가 있으면 프레임 하나를 재사용하고 없으면 프레임이 쌓이는 비교를 STEP으로 확인하세요.

재귀와 호출 스택의 배경

프로그래밍 언어에서는 LISP가 재귀를 핵심 도구로 삼았습니다. 매카시(John McCarthy)는 1960년 논문 "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I"에서 재귀 함수로 프로그램을 표현하는 방식을 소개했습니다. ALGOL 60 보고서는 프로시저 본문 안에서 자기 이름을 호출하는 것(재귀)을 허용했습니다.

꼬리 호출을 점프처럼 효율적으로 처리할 수 있다는 점은 스틸(Guy L. Steele)이 1977년 논문 "Debunking the 'Expensive Procedure Call' Myth"에서 논했습니다. 언어 표준이 이를 요구하는 예로 Scheme이 있고, 반대로 자바(javac, HotSpot 기준)와 CPython은 꼬리 호출 최적화를 하지 않습니다.

숫자로 확인하기

팩토리얼 fact(5) — fact(5)부터 fact(1)까지 프레임이 5개 쌓였다가 1, 2, 6, 24, 120을 차례로 반환합니다. 반복문은 result에 1, 2, 6, 24, 120이 되도록 변수 두 개만 갱신합니다.

fib(5)의 호출 — 호출은 모두 15번이고 서로 다른 n은 0부터 5까지 6가지입니다. fib(1)은 5번, fib(0)은 3번, fib(2)는 3번, fib(3)은 2번 계산되어 9번이 중복입니다.

호출 수의 증가 — fib(25)는 242,785번, fib(30)은 2,692,537번 호출됩니다. n이 1 늘 때 호출 수가 대략 1.6배씩 늘어납니다.

메모이제이션 — 계산한 값을 저장하면 fib(5)의 호출은 9번, 실제 계산은 6번입니다. fib(50)도 51개의 서로 다른 값만 계산해 12,586,269,025를 얻습니다.

꼬리 재귀 — fact_tail(5, 1)의 acc는 1, 5, 20, 60, 120으로 바뀌고 5번 호출됩니다. 최적화가 없는 환경에서는 프레임이 5개, 있으면 1개입니다.

코드 확인 — CPython은 기본 재귀 한도가 1000이고 fact_tail(5000)에서 RecursionError가 납니다. 자바는 기저 사례가 없는 재귀에서 StackOverflowError가 납니다.

자주 하는 오해

재귀는 항상 느리다 — 호출 오버헤드는 있지만 병합 정렬처럼 재귀로 쓴 분할정복도 O(n log n)입니다. 문제는 재귀 자체가 아니라 같은 계산을 되풀이하는 구조입니다.

꼬리 재귀로 쓰면 스택이 안 쌓인다 — 최적화는 언어와 컴파일러에 달려 있습니다. 자바와 CPython은 지원하지 않아 꼬리 재귀로 써도 깊이가 n까지 자랍니다.

반복으로 바꾸면 항상 점근적으로 빨라진다 — 메모이제이션 없는 재귀를 그대로 반복으로 옮기면 시간 복잡도는 같습니다. 줄어드는 것은 호출 오버헤드이고, 명시적 스택으로 옮기면 공간은 여전히 깊이에 비례하며 호출 스택 한도만 피합니다.

재귀 깊이는 입력 크기 n과 같다 — 팩토리얼은 n이지만 이진 탐색이나 병합 정렬은 깊이가 log n 정도입니다. 깊이는 문제를 얼마나 줄여 나가는지에 달려 있습니다.

기저 사례는 있으면 좋은 정도다 — 기저 사례가 없거나 도달하지 못하면 재귀가 끝나지 않고 스택 오버플로우로 끝납니다.

면접에서 이렇게 물어요

면접 질문

재귀와 반복의 차이는?

재귀는 자기 호출로 문제를 줄이며 호출마다 스택 프레임을 쓰고, 반복은 반복문으로 변수를 갱신합니다. 같은 계산이면 반복의 추가 공간이 보통 더 작습니다.

면접 질문

스택 오버플로우는 왜 나고 어떻게 피하나요?

깊은 재귀나 기저 사례 누락으로 프레임이 호출 스택을 가득 채우기 때문입니다. 반복문이나 명시적 스택으로 바꾸고, 가능하면 깊이를 줄입니다.

면접 질문

재귀 피보나치가 비효율적인 이유와 개선은?

같은 부분 문제를 중복 계산해 호출 수가 지수적으로 늘어납니다. 메모이제이션으로 저장하거나 반복문으로 이전 두 값만 들고 가면 덧셈을 상수 시간으로 볼 때 n에 비례합니다.

면접 질문

꼬리 호출 최적화란?

재귀 호출이 함수의 마지막 연산이면 호출 뒤에 할 일이 없으므로 이전 프레임을 재사용해 스택을 늘리지 않는 최적화입니다. 자바는 지원하지 않습니다.

활용 분야

트리와 그래프 탐색 — 트리 순회나 DFS는 재귀로 쓰면 구조가 그대로 드러납니다. 깊이가 클 때는 명시적 스택으로 바꿉니다.

분할정복과 백트래킹 — 병합 정렬, 퀵 정렬, 경우의 수를 탐색하는 백트래킹은 재귀로 표현합니다.

동적 계획법 — 재귀에 메모이제이션을 더한 하향식과 표를 채우는 반복문의 상향식이 같은 점화식을 풉니다.

함께 보면 좋은 토픽

스택과 큐 — 호출 스택의 바탕이 되는 후입선출 구조를 봅니다.

동적 계획법 기초 — 피보나치의 중복 계산을 저장으로 없애는 방법을 봅니다.

분할정복 — 재귀로 나누고 합치는 구조를 봅니다.

백트래킹 — 재귀로 경우의 수를 탐색하고 되돌아오는 과정을 봅니다.

참고 자료

논문 — McCarthy, J., "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I", Communications of the ACM 3(4), 1960

논문 — Steele, G. L., "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, LAMBDA: The Ultimate GOTO", ACM '77 (Seattle), 1977

교재 — Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms", 3rd ed., Chapter 4 Divide-and-Conquer (재귀식과 재귀 호출 트리)

공식 문서 — Python sys.getrecursionlimit (한도 조회·변경)

공식 문서 — Python functools.lru_cache

공식 문서 — Java StackOverflowError

Python — 재귀와 반복 팩토리얼, 호출 횟수 세기

def fact(n):
    return 1 if n <= 1 else n * fact(n - 1)     # 재귀: 호출마다 프레임이 쌓인다

def fact_iter(n):
    result = 1                                    # 반복: 깊이에 따라 늘어나는 프레임이 없다
    for i in range(2, n + 1):
        result *= i
    return result

print(fact(5), fact_iter(5))                 # 120 120

calls = 0
def fib(n):
    global calls
    calls += 1
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(5), calls)                         # 5 15
calls = 0
print(fib(25), calls)                        # 75025 242785

같은 팩토리얼을 재귀와 반복으로 쓴 예입니다. 재귀 fact(n)은 n × fact(n - 1)을 계산하려고 fact(n - 1)을 호출하고, 그 결과가 돌아올 때까지 현재 호출의 n을 스택 프레임에 들고 기다립니다. fact(5)는 fact(1)에서 멈출 때까지 프레임이 5개 쌓이고, 반환하며 하나씩 꺼내집니다. 반복 버전은 result와 i 두 변수만 갱신하므로 입력이 커져도 추가 공간이 O(1)입니다. 시각화의 호출 스택 탭이 보여 주는 과정과 같습니다. 아래쪽은 메모이제이션 없는 재귀 피보나치에서 호출 횟수를 센 결과입니다. fib(5)에서 15번, fib(25)에서 242,785번 호출됩니다. fib(n)이 fib(n - 1)과 fib(n - 2)를 각각 호출하므로 같은 값을 여러 번 다시 계산하고, n이 1 늘 때 호출 수가 대략 1.6배씩 늘어나 지수적으로 커집니다. 시각화의 중복 계산 탭이 보여 주는 호출 트리와 같습니다.

Python — 메모이제이션, 반복, 재귀 한도

import sys
from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)

print(fib_memo(50), fib_memo.cache_info().misses)   # 12586269025 51

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_iter(50))                       # 12586269025

print(sys.getrecursionlimit())                # 1000

def fact_tail(n, acc=1):                  # 꼬리 재귀: 곱셈을 호출 전에 끝낸다
    return acc if n <= 1 else fact_tail(n - 1, acc * n)

print(fact_tail(5))                      # 120
try:
    fact_tail(5000)
except RecursionError:
    print("RecursionError")               # 꼬리 재귀여도 파이썬은 깊이가 자란다
print(fact_iter(5000) > 0)                # True: 반복은 한도가 없다

중복 계산은 두 가지 방법으로 없앱니다. lru_cache는 계산한 인수와 결과를 저장해 fib_memo(50)에서 0부터 50까지 서로 다른 값 51개를 한 번씩만 계산합니다(cache_info의 misses가 51). 반복 버전 fib_iter는 이전 두 값만 들고 앞으로 나아가 변수 두 개로 같은 값을 얻습니다. CPython에는 재귀 깊이의 기본 한도가 있어 sys.getrecursionlimit()이 1000을 돌려줍니다. 깊이가 한도를 넘으면 RecursionError가 납니다. fact_tail은 곱셈을 호출 전에 acc에 끝내 둔 꼬리 재귀이지만, CPython은 꼬리 호출 최적화를 하지 않아 fact_tail(5000)에서도 같은 오류가 납니다. 반복문 fact_iter는 스택 깊이가 늘지 않으므로 5000에서도 계산됩니다. 시각화의 꼬리 호출 탭이 보여 주는 비교와 같습니다.

Java — 재귀, 반복, 메모이제이션과 스택 오버플로우

static long fact(int n) { return n <= 1 ? 1 : n * fact(n - 1); }

static long factIter(int n) {
    long r = 1;
    for (int i = 2; i <= n; i++) r *= i;
    return r;
}

static long[] memo = new long[91];
static long fibMemo(int n) {
    if (n < 2) return n;
    if (memo[n] != 0) return memo[n];                 // 이미 계산한 값
    return memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
}

static long depth(int n) { return depth(n + 1); }   // 기저 사례가 없는 재귀

// fact(5) = factIter(5) = 120, fibMemo(50) = 12586269025
// try { depth(0); } catch (StackOverflowError e) { ... }  → StackOverflowError

자바에서도 구조는 같습니다. 재귀 fact와 반복 factIter는 같은 값을 내고, fibMemo는 배열 memo에 계산한 값을 저장해 같은 n을 두 번 계산하지 않습니다. 이 저장 배열이 곧 메모이제이션입니다. 기저 사례가 없거나 깊이가 너무 깊은 재귀는 호출 스택이 가득 차 StackOverflowError를 던집니다. 스택 크기는 JVM 설정에 따라 다르므로 정확한 깊이는 실행 환경마다 다릅니다. 자바는 꼬리 호출 최적화를 하지 않으므로 꼬리 재귀로 고쳐도 깊이가 줄지 않고, 깊은 입력은 반복문이나 명시적 스택으로 바꿔야 합니다.

재귀 호출이 너무 깊어질 때 발생할 수 있는 문제는?

함수를 호출할 때마다 스택 프레임이 쌓입니다.

재귀 호출은 호출마다 스택에 프레임이 쌓이므로 깊이가 너무 깊으면 스택 공간을 초과해 스택 오버플로우가 발생합니다. 이런 경우 반복문이나 명시적 스택으로 바꿔야 할 수 있습니다.

꼬리 재귀 최적화(Tail Call Optimization)의 효과는? (지원하는 언어·컴파일러 기준)

호출 후에 할 일이 남아 있지 않다면 돌아올 곳을 저장할 필요가 없습니다.

재귀 호출 뒤에 남은 연산이 없는(꼬리 위치) 경우, 이전 프레임을 재사용해 스택 증가 없이 실행할 수 있습니다. 다만 Java처럼 이 최적화를 지원하지 않는 언어도 있습니다.

메모이제이션 없는 단순 재귀 피보나치가 비효율적인 이유는?

fib(5)를 구할 때 fib(3)이 몇 번 계산되는지 그려 보세요.

fib(n)은 fib(n-1)과 fib(n-2)를 각각 재귀 호출하므로 같은 값을 여러 번 다시 계산합니다. 호출 횟수가 대략 지수적으로 늘어나 비효율적이며, 메모이제이션이나 반복문으로 해결합니다.