재귀 함수

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

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

재귀 함수란 무엇인가?

재귀를 읽을 때는 전체 호출을 한꺼번에 펼치기보다, 종료 조건이 어디인지와 입력이 어떻게 작아지는지를 먼저 확인합니다.

아래 그림은 문제가 작아지고, 호출이 쌓였다가, 종료 조건에서 반환되는 흐름을 정리한 것입니다.

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

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

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

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

• 프랙탈 구조: 자기 유사성(self-similarity)을 가진 구조.
• 트리 또는 그래프 탐색: 계층적이거나 연결된 데이터 구조.
• 분할 정복(Divide and Conquer) 알고리즘: 문제를 더 작은 하위 문제로 분할하여 해결하는 방식 (예: 퀵 정렬, 병합 정렬).

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

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

n!은 n * (n-1) * (n-2) * ... * 1로 정의됩니다.

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

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

#include <iostream>

// n의 팩토리얼을 계산하는 재귀 함수
long long factorial(int n) {
    // 1. 기저 조건 (Base Case): 재귀 호출을 멈추는 조건
    if (n == 0 || n == 1) {
        return 1;
    }
    // 2. 재귀 단계 (Recursive Step): 자신을 호출하며 더 작은 문제로 분할
    else {
        std::cout << "factorial(" << n << ") 호출: " << n << " * factorial(" << n - 1 << ")" << std::endl;
        return n * factorial(n - 1);
    }
}

int main() {
    int num = 5;
    std::cout << num << "! = " << factorial(num) << std::endl;

    /* 출력 결과 (호출 과정):
    factorial(5) 호출: 5 * factorial(4)
    factorial(4) 호출: 4 * factorial(3)
    factorial(3) 호출: 3 * factorial(2)
    factorial(2) 호출: 2 * factorial(1)
    5! = 120
    */

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

    return 0;
}

이 과정에서 각 factorial 호출은 스택에 쌓이고, 기저 조건에 도달하여 반환이 시작되면 역순으로 계산 결과가 풀려나가면서 스택에서 제거됩니다.

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

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

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

#include <iostream>

// n번째 피보나치 수를 계산하는 재귀 함수
int fibonacci(int n) {
    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)를 호출하는 등, 동일한 계산이 여러 번 반복될 수 있습니다.

이는 재귀 함수의 잠재적인 비효율성을 보여줍니다.

재귀 함수 사용 시 주의사항

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

int fibonacciIterative(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;

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

재귀 vs 반복

모든 재귀 함수는 반복문으로 변환될 수 있고 모든 반복문은 재귀 함수로 변환될 수 있습니다.

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

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

• 재귀
  • 장점: 재귀적으로 정의된 문제(예: 트리 순회, 프랙탈)를 간결하고 우아하게 표현할 수 있습니다. 코드가 직관적이고 이해하기 쉬울 수 있습니다.
  • 단점: 스택 오버플로우 위험, 반복문보다 느리거나 비효율적일 수 있음.
• 반복
  • 장점: 일반적으로 재귀보다 빠르고 메모리 효율적입니다. 스택 오버플로우 위험이 없습니다.
  • 단점: 특정 문제(예: 트리 순회)에서는 재귀보다 코드가 복잡해지거나 직관적이지 않을 수 있습니다.

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

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

재귀를 선택할 때는 아름다운 코드보다 먼저 종료 조건, 문제 축소, 호출 깊이, 중복 계산을 확인해야 합니다.

아래 다이어그램은 재귀 구현을 제출하기 전의 최종 점검표입니다.

재귀 코드를 디버깅할 때는 결과값보다 먼저 기저 조건, 문제 축소, 호출 깊이, 중복 호출을 순서대로 추적하면 원인이 선명해집니다.