재귀 함수

함수가 자기 자신을 호출하는 특별한 형태의 함수, 즉 재귀 함수(Recursive Function)를 다룹니다.

재귀는 처음에는 다소 어렵게 느껴질 수 있지만, 특정 종류의 문제를 간결하게 표현할 수 있는 프로그래밍 기법입니다.

재귀 함수란 무엇인가?

재귀를 읽을 때는 전체 호출을 한꺼번에 펼치기보다, 함수가 받는 유효 입력, 종료 조건, 그리고 모든 재귀 경로에서 감소하는 값을 먼저 확인합니다.

아래 그림은 이 재귀 계약과 factorial(5)가 0! = 1까지 내려간 뒤 결과를 조합해 올라오는 흐름을 함께 정리한 것입니다.

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

재귀 함수는 자기 자신을 호출하여 작업을 수행하는 함수입니다.

마치 거울이 거울을 비추는 것처럼, 함수가 자신을 반복적으로 호출하며 문제를 해결해 나가는 방식입니다.

재귀 함수는 무한 루프에 빠지지 않기 위해 반드시 두 가지 요소를 포함해야 합니다.

재귀는 특히 다음과 같은 문제들을 해결하는 데 유용합니다.

• 프랙탈 구조: 자기 유사성(self-similarity)을 가진 구조.
• 트리 또는 그래프 탐색: 계층적이거나 연결된 데이터 구조. 순환 가능한 그래프에서는 같은 정점을 다시 방문하지 않도록 visited 집합 같은 별도 종료 장치가 필요합니다.
• 분할 정복(Divide and Conquer) 알고리즘: 문제를 더 작은 하위 문제로 분할하여 해결하는 방식 (예: 퀵 정렬, 병합 정렬).

재귀 함수의 예시: 팩토리얼 계산

가장 고전적이고 이해하기 쉬운 재귀 함수의 예시는 팩토리얼(Factorial) 계산입니다.

음이 아닌 정수 n에 대해 n!은 n * (n-1) * (n-2) * ... * 1로 정의됩니다. 음수는 이 예제 함수의 유효 입력이 아닙니다.

• 5! = 5 * 4 * 3 * 2 * 1
• 또한, 5! = 5 * (4!)와 같이 정의할 수도 있습니다.
• 4! = 4 * (3!)
• 1! = 1 (기저 조건)
• 0! = 1 (기저 조건)

이 정의를 바탕으로 팩토리얼 함수를 재귀적으로 구현해 봅시다.

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

// 이 구현의 계약: 0 <= n <= 20
std::int64_t factorial(int n) {
    if (n < 0) {
        throw std::invalid_argument("factorial requires n >= 0");
    }
    if (n > 20) {
        throw std::overflow_error("factorial exceeds the int64_t example range");
    }

    // 기저 조건
    if (n == 0) {
        return 1;
    }

    // 재귀 단계: n이 모든 호출에서 1씩 감소한다.
    std::cout << "factorial(" << n << ") 호출: "
              << n << " * factorial(" << n - 1 << ")\n";
    return n * factorial(n - 1);
}

int main() {
    int num = 5;
    const std::int64_t result = factorial(num);
    std::cout << num << "! = " << result << '\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
    */

    std::cout << "0! = " << factorial(0) << '\n'; // 출력: 0! = 1

    return 0;
}

factorial(5)는 5 → 4 → 3 → 2 → 1 → 0 순으로 호출되고, 0! = 1에서 멈춥니다. 이후 1 → 2 → 6 → 24 → 120 순으로 결과가 조합됩니다. 결과를 먼저 변수에 계산한 뒤 출력하므로 호출 추적과 최종 결과의 출력 순서도 코드에 적은 순서와 일치합니다.

이 구현은 정확히 64비트인 std::int64_t를 사용합니다. 20!은 들어가지만 21!은 들어가지 않으므로, 입력 경계에서 거부하여 signed 정수 오버플로우가 발생하기 전에 계산을 끝냅니다.

재귀 함수 예시: 피보나치 수열

피보나치 수열은 재귀의 또 다른 좋은 예시입니다.

피보나치 수열은 음이 아닌 정수 n에 대해 F(n) = F(n-1) + F(n-2)로 정의되며, F(0) = 0, F(1) = 1이 기저 조건입니다.

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

// 이 구현의 계약: 0 <= n <= 92
std::int64_t fibonacci(int n) {
    if (n < 0) {
        throw std::invalid_argument("fibonacci requires n >= 0");
    }
    if (n > 92) {
        throw std::overflow_error("fibonacci exceeds the int64_t example range");
    }
    if (n == 0) { // 첫 번째 기저 조건
        return 0;
    } else if (n == 1) { // 두 번째 기저 조건
        return 1;
    } else { // 재귀 단계
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main() {
    for (int i = 0; i < 10; ++i) {
        std::cout << "fibonacci(" << i << ") = " << fibonacci(i) << std::endl;
    }
    /* 출력:
    fibonacci(0) = 0
    fibonacci(1) = 1
    fibonacci(2) = 1
    fibonacci(3) = 2
    fibonacci(4) = 3
    fibonacci(5) = 5
    fibonacci(6) = 8
    fibonacci(7) = 13
    fibonacci(8) = 21
    fibonacci(9) = 34
    */
    return 0;
}

피보나치 함수는 factorial보다 더 복잡한 재귀 호출 구조를 가집니다.

fibonacci(5)를 계산하기 위해 fibonacci(4)와 fibonacci(3)을 호출하고, fibonacci(4)는 다시 fibonacci(3)과 fibonacci(2)를 호출하는 등, 동일한 계산이 여러 번 반복될 수 있습니다.

이는 재귀 함수의 잠재적인 비효율성을 보여줍니다. 반환형 std::int64_t의 표현 한계는 F(92)이지만, 위 순진한 재귀 구현으로 큰 입력을 계산하는 것은 지수적으로 늘어나는 중복 호출 때문에 실용적이지 않습니다. 큰 입력에는 반복·메모이제이션을 사용하고, F(93) 이상에는 임의 정밀도 정수 같은 다른 표현도 필요합니다.

재귀 함수 사용 시 주의사항

재귀 함수는 강력하고 우아하지만, 잘못 사용하면 심각한 문제를 야기할 수 있습니다.

#include <cstdint>
#include <stdexcept>

std::int64_t fibonacciIterative(int n) {
    if (n < 0) {
        throw std::invalid_argument("fibonacci requires n >= 0");
    }
    if (n > 92) {
        throw std::overflow_error("fibonacci exceeds the int64_t example range");
    }
    if (n == 0) return 0;
    if (n == 1) return 1;

    std::int64_t a = 0;
    std::int64_t b = 1;
    std::int64_t result = 0;
    for (int i = 2; i <= n; ++i) {
        result = a + b;
        a = b;
        b = result;
    }
    return result;
}

재귀 vs 반복

계산 가능성의 관점에서는 재귀를 명시적 상태와 스택을 쓰는 반복으로 모사하거나 반복을 재귀로 표현할 수 있습니다. 그러나 이것이 언제나 단순한 for 문으로 바뀌거나, 같은 자원 사용량·예외 안전성·관찰 가능한 동작을 자동으로 보존한다는 뜻은 아닙니다.

둘 중 어떤 것을 사용할지는 문제의 특성, 코드의 가독성, 그리고 성능 고려 사항에 따라 달라집니다.

다음 판단 기준은 재귀를 유지할지, 반복문이나 메모이제이션으로 바꿀지 빠르게 가르는 기준입니다.

• 재귀
  • 장점: 재귀적으로 정의된 문제(예: 트리 순회, 프랙탈)를 간결하고 우아하게 표현할 수 있습니다. 코드가 직관적이고 이해하기 쉬울 수 있습니다.
  • 단점: 스택 오버플로우 위험, 반복문보다 느리거나 비효율적일 수 있음. C++는 꼬리 호출 최적화를 보장하지 않으므로 tail-recursive 형태라도 스택을 쓰지 않는다고 가정해서는 안 됩니다. 실제 최적화 여부는 컴파일러와 빌드 설정에 따라 달라집니다.
• 반복
  • 장점: 일반적으로 재귀보다 빠르고 메모리 효율적일 수 있으며, 재귀 깊이에 비례해 호출 프레임이 늘어나는 위험을 피합니다.
  • 단점: 특정 문제(예: 트리 순회)에서는 재귀보다 코드가 복잡해지거나 직관적이지 않을 수 있습니다.

핵심: 재귀 함수를 사용할 때는 항상 기저 조건을 명확히 설정하고, 각 재귀 호출이 원래 문제보다 더 작은 문제로 나아가는지 확인하여 무한 재귀에 빠지지 않도록 주의해야 합니다.

성능이 중요한 경우에는 재귀 대신 반복문을 고려하거나, 메모이제이션 같은 최적화 기법을 적용해야 합니다.

재귀를 선택할 때는 아름다운 코드보다 먼저 유효 입력, 기저 조건, 모든 경로의 문제 축소, 최악 호출 깊이, 중복 계산을 확인해야 합니다. 순환 가능한 그래프라면 visited 상태도 종료 계약의 일부입니다.