재귀 함수

함수 안에서 다른 함수를 호출할 수 있듯이, 함수가 자기 자신을 호출할 수도 있습니다. 이런 함수를 재귀 함수(recursive function)라고 하며, 큰 문제를 같은 모양의 더 작은 문제로 나누어 풀 때 코드를 간결하게 만들어 줍니다.

이 글은 재귀가 끝나기 위한 조건, 팩토리얼과 피보나치 수열을 재귀로 계산하는 과정, 재귀를 쓸 때의 위험과 반복문과의 비교를 다룹니다. 함수의 정의와 호출에서 본 것처럼 호출마다 매개변수가 새로 만들어진다는 점이 재귀를 이해하는 출발점입니다.

기저 조건과 재귀 단계

재귀 함수에는 두 부분이 꼭 있어야 합니다. 더 이상 자기를 호출하지 않고 바로 결과를 돌려주는 기저 조건(base case)과, 원래보다 작은 입력으로 자기를 호출하는 재귀 단계(recursive step)입니다. 재귀 단계가 매번 입력을 줄여 언젠가 기저 조건에 닿아야 호출이 끝납니다.

재귀 함수를 읽을 때는 호출 전체를 한꺼번에 펼치기보다, 먼저 세 가지를 확인합니다. 어떤 입력을 받을 수 있는지, 기저 조건이 무엇인지, 그리고 모든 재귀 경로에서 줄어드는 값이 있는지입니다. 이 세 가지가 맞으면 나머지는 한 단계의 계산만 믿고 읽으면 됩니다.

팩토리얼

음이 아닌 정수 n의 팩토리얼 n!은 1부터 n까지의 곱이며, 0!은 1로 정합니다. 5! = 5 × 4!처럼 n! = n × (n - 1)!로 쓸 수 있으므로, 그대로 재귀 함수가 됩니다.

#include <cstdint>
#include <iostream>
#include <stdexcept>

// 받을 수 있는 입력: 0 <= n <= 20
std::int64_t factorial(int n) {
    if (n < 0 || n > 20) {
        throw std::out_of_range("factorial requires 0 <= n <= 20");
    }
    if (n == 0) {
        return 1;
    }
    std::cout << "factorial(" << n << ") = " << n
              << " * factorial(" << n - 1 << ")\n";
    return n * factorial(n - 1);
}

int main() {
    const std::int64_t result = factorial(5);
    std::cout << "5! = " << result << '\n';
    std::cout << "0! = " << factorial(0) << '\n';
}

factorial(5) = 5 * factorial(4)
factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1 * factorial(0)
5! = 120
0! = 1

factorial(5)는 5 * factorial(4)를 계산하려고 factorial(4)를 호출하고, 그 결과가 올 때까지 곱셈을 미뤄 둡니다. 아래 그림처럼 호출은 5, 4, 3, 2, 1, 0으로 내려가고, 기저 조건인 factorial(0)이 1을 돌려준 뒤에야 미뤄 둔 곱셈이 1, 2, 6, 24, 120의 순서로 계산되며 올라옵니다. 각 호출의 n은 서로 다른 변수이므로, 돌아올 때 그 호출 자신의 n을 곱합니다.

factorial(5)
└─ 5 × factorial(4)
   └─ 4 × factorial(3)
      └─ 3 × factorial(2)
         └─ 2 × factorial(1)
            └─ 1 × factorial(0)
               └─ 1  // base

0! = 1
1! = 1 × 1  = 1
2! = 2 × 1  = 2
3! = 3 × 2  = 6
4! = 4 × 6  = 24
5! = 5 × 24 = 120

factorial(5)
└─ 5 × factorial(4)
   └─ 4 × factorial(3)
      └─ 3 × factorial(2)
         └─ 2 × factorial(1)
            └─ 1 × factorial(0)
               └─ 1  // base

0! = 1
1! = 1 × 1  = 1
2! = 2 × 1  = 2
3! = 3 × 2  = 6
4! = 4 × 6  = 24
5! = 5 × 24 = 120

std::int64_t는 <cstdint>의 정확히 64비트인 부호 있는 정수 타입이며, 20!은 담을 수 있지만 21!은 범위를 넘습니다. 그래서 이 함수는 받을 수 있는 입력을 0부터 20까지로 정하고, 범위 밖의 입력은 계산하기 전에 throw로 거부해 부호 있는 정수의 오버플로를 막습니다. 그림은 음수와 20보다 큰 값을 각각 입력 오류와 범위 오류로 나누어 적었지만, 이 코드는 두 경우를 같은 std::out_of_range로 던집니다. throw는 정상적인 결과 대신 오류를 알리는 예외(exception)이며, 예외 처리의 기본 개념에서 자세히 다룹니다. 이 예제는 예외를 잡지 않으므로, 범위 밖의 값을 넣으면 프로그램이 정상 출력 없이 끝납니다.

피보나치 수열

피보나치 수열은 F(0) = 0, F(1) = 1이고, 그 뒤로는 F(n) = F(n - 1) + F(n - 2)인 수열입니다. 기저 조건이 두 개이고, 재귀 단계가 자기를 두 번 호출합니다.

#include <cstdint>
#include <iostream>

// 받을 수 있는 입력: 0 <= n <= 92
std::int64_t fibonacci(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    for (int i = 0; i < 10; ++i) {
        std::cout << fibonacci(i) << ' ';
    }
    std::cout << '\n';
}

0 1 1 2 3 5 8 13 21 34

이 함수는 정의를 그대로 옮겨 읽기 쉽지만, 같은 계산을 여러 번 반복합니다. fibonacci(5)는 fibonacci(4)와 fibonacci(3)을 호출하고, fibonacci(4)가 다시 fibonacci(3)을 호출하므로 fibonacci(3)이 두 번 계산됩니다. 입력이 하나 커질 때마다 호출 수가 대략 1.6배씩 늘어나, 40 정도만 되어도 호출이 수억 번에 이릅니다. std::int64_t로는 F(92)까지 담을 수 있지만, 이 방식으로 그만큼 큰 값을 계산하는 것은 현실적이지 않습니다.

재귀의 위험

함수를 호출할 때마다 매개변수와 지역 변수, 돌아갈 위치를 보관할 공간이 필요하며, 보통은 호출 스택(call stack)에 쌓입니다. 재귀가 너무 깊어지면 이 공간이 모자라 프로그램이 비정상 종료되는 스택 오버플로(stack overflow)가 생길 수 있습니다. 얼마나 깊이 들어갈 수 있는지는 운영체제, 스레드의 스택 크기, 컴파일러와 최적화 옵션, 호출 하나가 쓰는 공간에 따라 다르므로, 특정 숫자를 안전한 한계로 가정하지 않습니다.

기저 조건이 빠지거나 어떤 경로에서 입력이 줄지 않으면, 재귀는 끝나지 않고 스택 오버플로로 이어집니다. 앞의 factorial에서 return n * factorial(n - 1);을 factorial(n)으로 잘못 쓰면 n이 줄지 않아, 올바른 입력에서도 0에 닿지 않습니다. 이런 코드는 실행해서 한계를 시험하기보다, 모든 경로에서 줄어드는 값이 있는지로 판단합니다.

C++ 표준은 꼬리 호출 최적화(tail call optimization)를 보장하지 않습니다. 함수의 마지막 동작이 자기 호출인 꼬리 재귀 형태라도, GCC가 -O2에서 호출을 반복으로 바꿀 수는 있지만 최적화를 끈 빌드에서는 그대로 스택을 씁니다. 그래서 꼬리 재귀라는 이유만으로 깊은 재귀가 안전하다고 여기지 않습니다.

더 깊이: 스택 크기와 꼬리 호출을 정하는 곳

Windows 실행 파일에서 주 스레드가 쓸 스택의 크기는 링크할 때 실행 파일에 기록됩니다. MSVC의 링커는 /STACK 옵션으로 이 값을 정하며 x64의 기본 예약 크기는 1MB이고, MSYS2의 GCC가 쓰는 GNU 링커는 PE 형식을 대상으로 할 때 --stack 옵션을 받으며 기본으로 2MB를 예약합니다. 그래서 같은 재귀 함수라도 어느 도구로 링크했는지에 따라 버틸 수 있는 깊이가 다르고, GNU 링커라면 g++ main.cpp -Wl,--stack,8388608처럼 링커 옵션을 넘겨 늘릴 수 있습니다. 다만 스택을 늘리는 것은 깊이가 입력에 비례하는 재귀의 근본적인 해결이 아니므로, 반복문으로 바꾸는 쪽을 먼저 봅니다.

꼬리 호출을 점프로 바꾸는 최적화는 GCC에서 -foptimize-sibling-calls 옵션이 맡으며, 이 옵션은 -O2, -O3, -Os에서 켜집니다. 반드시 꼬리 호출이어야 하는 곳에는 함수 호출을 돌려주는 return 문 앞에 속성을 붙일 수 있는데, GCC는 15부터 [[gnu::musttail]]와 [[clang::musttail]]를 모두 받고 Clang은 [[clang::musttail]]를 받습니다. GCC 문서에 따르면 이 속성은 그 호출이 스택을 더 쓰지 않는 꼬리 호출이어야 한다고 요구하며, 그렇게 만들 수 없으면 컴파일러가 오류를 냅니다.

반복문으로 바꾸기

같은 하위 문제를 반복해서 계산하거나 재귀가 깊어질 수 있다면, 반복문으로 바꾸는 것을 생각합니다. 피보나치 수열은 앞의 두 값만 기억하면 다음 값을 구할 수 있습니다.

#include <cstdint>

std::int64_t fibonacciIterative(int n) {
    if (n == 0) {
        return 0;
    }
    std::int64_t previous = 0;
    std::int64_t current = 1;
    for (int i = 2; i <= n; ++i) {
        const std::int64_t next = previous + current;
        previous = current;
        current = next;
    }
    return current;
}

이 함수는 n이 1 이상이면 반복문을 n - 1번 돌아 계산하고, 호출이 쌓이지 않으므로 n이 92여도 바로 끝납니다. 계산한 결과를 배열에 저장해 두었다가 다시 쓰는 메모이제이션(memoization)으로 재귀 형태를 유지하면서 중복 계산만 없앨 수도 있습니다.

위 그림처럼 구현 방식은 네 가지 점검으로 고릅니다. 먼저 기저 조건과 모든 경로에서 줄어드는 값을 확인하고, 그다음 평균이 아니라 가장 깊어지는 경우의 호출 깊이를 계산합니다. 같은 하위 문제를 다시 계산하면 메모이제이션이나 반복문을 고려하고, 순환이 있을 수 있는 그래프를 탐색한다면 이미 방문한 곳을 기록해 같은 곳을 다시 들어가지 않게 합니다.

재귀가 잘 맞는 곳은 트리 탐색이나 분할 정복처럼 문제 자체가 같은 모양의 하위 문제로 나뉘고, 깊이가 입력 크기의 로그 정도로 제한되는 경우입니다. 반대로 한쪽으로 치우친 트리처럼 깊이가 입력 크기만큼 늘어날 수 있다면, 반복문과 명시적인 스택으로 바꾸는 편이 안전합니다.

정리

• 재귀 함수는 바로 결과를 돌려주는 기저 조건과, 더 작은 입력으로 자기를 호출하는 재귀 단계로 이루어집니다.
• 모든 재귀 경로에서 입력이 줄어 기저 조건에 닿아야 하며, 받을 수 있는 입력의 범위도 함께 정합니다.
• 각 호출의 매개변수는 서로 다른 변수이고, 미뤄 둔 계산은 기저 조건에서 돌아올 때 차례로 이루어집니다.
• 재귀가 깊으면 스택 오버플로가 생길 수 있고, C++은 꼬리 호출 최적화를 보장하지 않습니다.
• 같은 하위 문제를 반복 계산하는 재귀는 반복문이나 메모이제이션으로 바꿉니다.

연습 문제

1. 더 작은 입력 따라가기

factorial.cpp에서 factorial(5)를 factorial(3)으로 바꾸면 호출 메시지는 몇 줄이고 마지막 결과는 무엇인가요? 이어서 호출하는 factorial(0)은 메시지를 출력하나요?

2. 호출 횟수 세기

fibonacci(5)를 한 번 호출하면 fibonacci 함수는 자기 자신을 포함해 모두 몇 번 호출되나요?

3. 기저 조건을 건너뛰는 입력

다음 함수에 4를 넘기면 어떻게 되나요? 5를 넘기면 어떻게 되며, 어떻게 고치면 되나요?

int countByTwo(int n) {
    if (n == 0) {
        return 0;
    }
    return 1 + countByTwo(n - 2);
}

이것으로 6장의 함수를 마칩니다. 다음 장의 포인터 기초에서는 변수의 값 대신 변수가 있는 메모리 주소를 담는 포인터를 다루며, 함수가 호출한 쪽의 변수를 직접 바꾸는 방법으로도 이어집니다.