2025-09-03 01:33

• 재귀는 큰 문제를 동일한 구조의 더 작은 문제로 나누어 해결하는 프로그래밍 기법입니다.

• 모든 재귀 함수는 무한 반복을 막는 ‘탈출 조건(Base Case)‘과 자기 자신을 다시 호출하는 ‘재귀 호출(Recursive Step)‘로 구성됩니다.

• 코드를 간결하게 만들지만, 메모리 사용량이 많아 스택 오버플로우를 유발할 수 있으므로 신중하게 사용해야 합니다.

재귀 함수 호출의 모든 것 기초부터 심화까지

컴퓨터 과학의 세계에는 처음 들으면 마치 마법처럼 느껴지는 개념들이 있습니다. ‘재귀(Recursion)‘는 그중에서도 가장 우아하고 강력한 마법 중 하나일 것입니다. 자기 자신을 끊임없이 호출하며 복잡한 문제를 해결해 나가는 모습은 마치 무한한 거울 속에 비친 자신의 모습을 보는 것과 같습니다.

하지만 많은 개발자들이 재귀의 아름다움 뒤에 숨겨진 복잡함에 좌절하곤 합니다. 이 핸드북은 재귀라는 마법의 원리를 파헤치고, 여러분이 자신감 있게 재귀를 사용할 수 있도록 돕기 위해 만들어졌습니다. 재귀가 왜 만들어졌는지부터 시작해 그 구조를 분석하고, 실제 사용법을 익히며, 심화 개념까지 차근차근 정복해 봅시다.

1. 재귀는 왜 만들어졌을까? (탄생 배경)

재귀를 이해하는 가장 좋은 방법은 ‘왜 이런 개념이 필요했을까?‘라는 질문에서 시작하는 것입니다. 컴퓨터가 해결해야 할 문제들 중에는 ‘문제의 구조가 전체와 부분이 닮아있는’ 형태가 많습니다.

가장 직관적인 예시는 **러시아 인형(마트료시카)**입니다. 가장 큰 인형을 열면 그보다 조금 작은 인형이 나오고, 그 인형을 열면 또 더 작은 인형이 나옵니다. 이 과정은 ‘더 이상 열 수 없는’ 가장 작은 인형을 만날 때까지 반복됩니다. 여기서 핵심은 ‘인형을 연다’는 행위가 모든 크기의 인형에 동일하게 적용된다는 것입니다.

이처럼 문제의 정의 자체가 자기 자신을 포함하고 있을 때, 재귀는 가장 자연스럽고 우아한 해결책이 됩니다. 억지로 복잡한 반복문을 사용하는 대신, 문제의 본질적인 구조를 코드에 그대로 반영할 수 있게 해주는 것이죠.

비유로 이해하기: “사전에서 단어 찾기” ‘재귀’라는 단어를 찾기 위해 사전을 폈다고 상상해 보세요. 설명에 “재귀적(recursive) 방법을 참고하라”고 쓰여 있습니다. 그래서 ‘재귀적’을 찾아보니 “재귀(recursion)를 사용하는 것”이라고 되어 있습니다. 이것이 바로 재귀의 본질입니다. 단, 이 과정이 끝나려면 “더 이상 다른 단어를 참고할 필요가 없는” 명확한 설명이 있어야 합니다. 이것이 바로 재귀의 ‘탈출 조건’입니다.

2. 재귀의 해부학: 두 가지 핵심 요소

모든 재귀 함수는 반드시 두 가지 핵심 요소로 구성됩니다. 이 둘 중 하나라도 빠지면 함수는 제대로 동작하지 않거나 영원히 끝나지 않는 무한 루프에 빠지게 됩니다.

1) 탈출 조건 (Base Case)

재귀의 멈춤 신호입니다. 러시아 인형의 가장 작은 인형처럼, 더 이상 문제를 쪼갤 수 없는 최소 단위의 상태를 정의합니다. 함수는 이 조건에 도달했을 때, 자신을 다시 호출하는 것을 멈추고 구체적인 값을 반환하며 기나긴 호출의 여정을 마무리 짓습니다.

탈출 조건이 없는 재귀 함수는 “브레이크 없는 자동차”와 같습니다. 끝없이 자기 자신을 호출하다가 결국 스택 오버플로우(Stack Overflow) 라는 치명적인 에러를 내뿜고 멈추게 됩니다. (이 개념은 뒤에서 더 자세히 다룹니다.)

2) 재귀 호출 (Recursive Step)

문제를 잘게 쪼개는 과정입니다. 현재 해결해야 할 문제를 탈출 조건에 한 걸음 더 가까워지는 형태로 변형한 뒤, 자기 자신을 다시 호출하는 부분입니다.

예를 들어 ‘10개의 상자를 여는 문제’가 있다면, 재귀 호출은 ‘일단 상자 하나를 열고, 남은 9개의 상자를 여는 문제’로 바꾸어 자기 자신에게 다시 던져주는 것과 같습니다. 이 과정이 반복되면서 문제는 점점 작아지고, 마침내 ‘남은 상자가 0개인’ 탈출 조건에 도달하게 됩니다.

3. 재귀 사용법: 클래식 예제로 배우기

이제 실제 코드를 통해 재귀가 어떻게 동작하는지 살펴보겠습니다. 예제는 간결하고 이해하기 쉬운 Python 코드를 사용하겠습니다.

예제 1: 팩토리얼 (Factorial)

팩토리얼은 재귀를 설명할 때 가장 먼저 등장하는 단골 예제입니다. N!은 1부터 N까지의 모든 정수를 곱한 값입니다.

• 5! = 5 * 4 * 3 * 2 * 1 = 120

이것을 재귀적으로 정의하면 다음과 같습니다.

• n! = n * (n-1)!

# 팩토리얼을 계산하는 재귀 함수
def factorial(n):
    # 1. 탈출 조건 (Base Case)
    # n이 1일 때, 더 이상 쪼갤 수 없으므로 1을 반환하고 멈춘다.
    if n == 1:
        return 1
    # 2. 재귀 호출 (Recursive Step)
    # n과 (n-1)의 팩토리얼 결과를 곱한다.
    else:
        return n * factorial(n - 1)
 
# 함수 호출
print(f"5! = {factorial(5)}") # 출력: 5! = 120

factorial(5)가 호출되는 과정은 다음과 같습니다.

factorial(5) = 5 * factorial(4)
             = 5 * (4 * factorial(3))
             = 5 * (4 * (3 * factorial(2)))
             = 5 * (4 * (3 * (2 * factorial(1))))
             = 5 * (4 * (3 * (2 * 1))) # 탈출 조건 도달!
             = 120

예제 2: 피보나치 수열 (Fibonacci Sequence)

피보나치 수열은 각 항이 바로 앞의 두 항의 합으로 이루어지는 수열입니다 (0, 1, 1, 2, 3, 5, 8, ...).

• F(n) = F(n-1) + F(n-2)

이 정의 자체가 재귀적이기 때문에 코드로 옮기기 매우 쉽습니다.

# 피보나치 수열의 n번째 항을 구하는 재귀 함수
def fibonacci(n):
    # 1. 탈출 조건 (Base Case)
    # n이 0 또는 1일 경우, 각각 0과 1을 반환한다.
    if n <= 1:
        return n
    # 2. 재귀 호출 (Recursive Step)
    # n-1번째 항과 n-2번째 항의 합을 반환한다.
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# 함수 호출
print(f"피보나치 수열의 6번째 항은? {fibonacci(6)}") # 출력: 피보나치 수열의 6번째 항은? 8

이 코드는 재귀의 간결함을 잘 보여주지만, fibonacci(5)를 구하기 위해 fibonacci(4)와 fibonacci(3)을 호출하고, fibonacci(4)는 또 fibonacci(3)과 fibonacci(2)를 호출하는 등 동일한 계산이 매우 비효율적으로 반복된다는 단점이 있습니다. (이는 ‘심화 내용’에서 해결합니다.)

4. 재귀 vs 반복: 무엇을 선택해야 할까?

재귀로 풀 수 있는 모든 문제는 반복문(for, while)으로도 풀 수 있으며, 그 반대도 마찬가지입니다. 그렇다면 언제 재귀를 쓰고, 언제 반복문을 써야 할까요?

특징	재귀 (Recursion)	반복 (Iteration)
코드 가독성	문제의 구조를 직관적으로 표현하여 코드가 간결하고 이해하기 쉬운 경우가 많다. (예: 트리 순회)	코드가 길어지고 복잡해질 수 있지만, 로직의 흐름이 명시적으로 드러난다.
성능	함수 호출에 따른 오버헤드가 발생하여 일반적으로 반복문보다 느리다.	추가적인 함수 호출이 없어 성능 면에서 더 효율적이다.
메모리 사용량	호출될 때마다 호출 스택에 메모리가 쌓여, 깊이가 깊어지면 스택 오버플로우가 발생할 수 있다.	정해진 변수만 사용하여 메모리 사용량이 일정하고 예측 가능하다.
적합한 문제 유형	분할 정복(Divide and Conquer), 트리/그래프 탐색, 백트래킹 등 문제의 구조가 재귀적인 경우	선형적인 데이터 구조를 순회하거나, 정해진 횟수만큼 동일한 작업을 반복하는 경우

결론: “정답은 없다. 상황에 맞게 사용하라.”

• 재귀를 우선 고려할 때: 문제 자체가 재귀적으로 정의되어 있고, 코드의 간결함과 가독성이 중요할 때. (예: DFS, 하노이의 탑)

• 반복문을 우선 고려할 때: 성능이 매우 중요하거나, 재귀의 깊이가 예측할 수 없을 정도로 깊어질 가능성이 있을 때.

5. 심화 내용: 재귀의 이면 들여다보기

1) 호출 스택 (Call Stack)과 스택 오버플로우 (Stack Overflow)

재귀 함수의 동작 원리를 이해하려면 ‘호출 스택’을 알아야 합니다. 호출 스택은 함수가 호출될 때마다 해당 함수의 정보(매개변수, 지역 변수, 복귀 주소 등)를 차곡차곡 쌓아두는 메모리 공간입니다.

factorial(3)을 예로 들면, 스택은 다음과 같이 쌓입니다.

1. main()이 factorial(3) 호출 → [ factorial(3) ]

2. factorial(3)이 factorial(2) 호출 → [ factorial(3), factorial(2) ]

3. factorial(2)가 factorial(1) 호출 → [ factorial(3), factorial(2), factorial(1) ]

factorial(1)이 탈출 조건에 도달해 1을 반환하면, 스택의 가장 위에서부터 하나씩 처리되며 빠져나옵니다.

• factorial(1) 반환 → [ factorial(3), factorial(2) ]

• factorial(2)는 1을 받아 2 * 1 = 2를 반환 → [ factorial(3) ]

• factorial(3)은 2를 받아 3 * 2 = 6을 반환 → [ ] (스택 비워짐)

스택 오버플로우는 이 스택 공간이 가득 차서 더 이상 새로운 함수 정보를 쌓을 수 없을 때 발생하는 에러입니다. 재귀의 깊이가 너무 깊어지거나(예: factorial(10000)), 탈출 조건이 없을 때 발생합니다.

2) 꼬리 재귀 최적화 (Tail Call Optimization)

일부 언어(예: Scheme, Scala)에서는 특정 형태의 재귀를 최적화하여 스택 오버플로우를 방지합니다. 꼬리 재귀란, 재귀 호출이 함수의 가장 마지막 작업으로 수행되는 형태를 말합니다.

# 일반 재귀 (꼬리 재귀 아님)
def factorial(n):
    if n == 1: return 1
    return n * factorial(n - 1) # factorial(n-1) 호출 후 곱셈 작업이 남음

# 꼬리 재귀 형태
def tail_factorial(n, accumulator=1):
    if n == 1:
        return accumulator
    return tail_factorial(n - 1, accumulator * n) # 재귀 호출이 마지막 작업임

꼬리 재귀 최적화를 지원하는 컴파일러는 이런 코드를 발견하면, 새로운 스택을 쌓는 대신 기존 스택을 재활용하는 방식으로 코드를 변환합니다. 이는 사실상 반복문과 동일한 방식으로 동작하게 되어 스택 오버플로우의 위험이 사라집니다. (단, 안타깝게도 파이썬은 공식적으로 꼬리 재귀 최적화를 지원하지 않습니다.)

3) 메모이제이션 (Memoization)

앞서 본 피보나치 함수의 비효율성을 해결하는 강력한 기법입니다. 메모이제이션은 이전에 계산한 값을 저장해두고, 동일한 계산이 필요할 때 다시 계산하는 대신 저장된 값을 가져와 사용하는 것입니다. 일종의 ‘캐싱(Caching)’ 기법입니다.

# 메모이제이션을 적용할 딕셔너리
memo = {}

def fibonacci_memo(n):
    # 이미 계산한 값이면 바로 반환
    if n in memo:
        return memo[n]
    
    # 탈출 조건
    if n <= 1:
        result = n
    # 재귀 호출
    else:
        result = fibonacci_memo(n-1) + fibonacci_memo(n-2)
    
    # 결과를 저장하고 반환
    memo[n] = result
    return result

print(f"메모이제이션 적용 후, 피보나치 30번째 항: {fibonacci_memo(30)}")

메모이제이션을 적용하면, fibonacci(3)과 같은 동일한 함수가 여러 번 호출되더라도 실제 계산은 단 한 번만 일어나므로 속도가 극적으로 향상됩니다. 이는 동적 계획법(Dynamic Programming)의 핵심 아이디어 중 하나입니다.

결론: 재귀와 친해지기

재귀는 단지 코딩 기술이 아니라 문제를 바라보는 새로운 관점을 제공합니다. 복잡하고 거대한 문제를 더 작고 관리하기 쉬운 단위로 쪼개어 생각하는 훈련은 모든 개발자에게 필수적입니다.

처음에는 재귀적인 사고방식이 어색할 수 있습니다. 하지만 이 핸드북에서 다룬 예제들을 직접 따라 해보고, 왜 탈출 조건이 필요한지, 호출 스택이 어떻게 쌓이는지 머릿속으로 그려보는 연습을 반복하다 보면 어느새 재귀라는 강력한 도구를 자유자재로 사용하는 자신을 발견하게 될 것입니다.

레퍼런스(References)

재귀