[C/C++] 17. 재귀 함수(2)

앞서 재귀 함수의 동작 원리와 호출 스택(Call Stack), 그리고 필수적인 탈출 조건에 대해 알아보았다. 이번 글에서는 재귀 함수의 대표적인 활용 예시인 팩토리얼(Factorial)과 피보나치 수열(Fibonacci Sequence)을 반복문과 재귀 함수 두 가지 방식으로 직접 구현해보고, 각 방식의 구현 직관성과 성능 차이를 정리한다.

1. 재귀 함수로 구현한 팩토리얼(Factorial)

팩토리얼( $n!$ )의 수학적 정의인 $n! = n \times (n-1)!$ 을 코드로 그대로 옮기면 매우 직관적인 재귀 함수가 완성된다.

#include <stdio.h>
 
// 재귀 함수 버전 팩토리얼
int FactorialRecursive(int n) {
    // 1. 탈출 조건 (Base Case): 1!은 1이므로 재귀 호출을 멈추고 1 반환
    if (n <= 1) {
        return 1;
    }
    // 2. 재귀 호출: n! = n * (n-1)!
    return n * FactorialRecursive(n - 1);
}
 
int main() {
    int target = 4;
    int result = FactorialRecursive(target);
    printf("재귀: %d! = %d\n", target, result); // 결과: 24
    return 0;
}

동작 원리: FactorialRecursive(4) 호출 시, 스택에는 4 * FactorialRecursive(3), 3 * FactorialRecursive(2), 2 * FactorialRecursive(1) 순으로 스택 프레임이 쌓인다. 마지막 FactorialRecursive(1)이 탈출 조건을 만나 1을 반환하면, 스택이 역으로 터지며(2 * 1, 3 * 2, 4 * 6) 최종 결과 24가 계산된다.

2. 피보나치 수열(Fibonacci Sequence)의 두 가지 구현

피보나치 수열은 첫 두 숫자가 1, 1로 시작하며, 세 번째 숫자부터는 바로 앞 두 숫자의 합으로 구성되는 수열이다. (예: 1, 1, 2, 3, 5, 8, 13, ...)

1) 반복문(for)을 이용한 구현

반복문을 사용하여 $n$ 번째 피보나치 수를 구하려면, 이전 두 값을 저장할 변수(prev1, prev2)를 두고 루프를 돌며 이 값들을 계속해서 갱신해주어야 한다.

#include <stdio.h>
 
// 반복문 버전 피보나치
int FibonacciIterative(int n) {
    if (n <= 2) {
        return 1;
    }
 
    int prev2 = 1; // n-2번째 값
    int prev1 = 1; // n-1번째 값
    int current = 0;
 
    // 세 번째부터 n번째까지 반복 계산
    for (int i = 3; i <= n; ++i) {
        current = prev1 + prev2; // 현재 값 계산
        // 변수 값 갱신 (순서 주의: prev2를 먼저 갱신하면 원본 값을 잃음)
        prev2 = prev1; 
        prev1 = current;
    }
    return current;
}
 
int main() {
    int n = 7;
    int result = FibonacciIterative(n);
    printf("반복문: %d번째 피보나치 수 = %d\n", n, result); // 결과: 13
    return 0;
}

특징: 변수 값을 갱신하는 논리가 직관적이지 않을 수 있어 구현 시 종이에 변수 값의 변화를 시각화해보는 것이 좋다. 하지만 연산 속도는 $O(n)$ 으로 매우 빠르다.

2) 재귀 함수를 이용한 구현

피보나치 수열의 정의인 $F(n) = F(n-1) + F(n-2)$ (단, $F(1)=F(2)=1$ )을 코드로 옮기면 코드가 매우 간결하고 가독성이 뛰어나다.

#include <stdio.h>
 
// 재귀 함수 버전 피보나치
int FibonacciRecursive(int n) {
    // 1. 탈출 조건: 첫 번째 또는 두 번째는 1 반환
    if (n <= 2) {
        return 1;
    }
    // 2. 재귀 호출: 두 갈래로 나뉘어 호출됨
    return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2);
}
 
int main() {
    int n = 7;
    int result = FibonacciRecursive(n);
    printf("재귀: %d번째 피보나치 수 = %d\n", n, result); // 결과: 13
    return 0;
}

특징: 구현의 가독성은 극대화되지만, 함수가 두 갈래로 나뉘어 폭발적으로(기하급수적으로) 재귀 호출을 일으킨다. $n$ 이 커질수록 호출 횟수가 수십억 번을 넘어가 성능이 심각하게 저하된다.

마무리하며

재귀 함수의 강력함: 팩토리얼이나 피보나치 수열처럼 수학적 정의 자체가 재귀적이거나, 트리(Tree)와 같은 계층적 자료구조를 다룰 때 재귀 함수는 코드를 매우 간결하고 직관적으로 만든다.
성능적 한계: 피보나치 수열의 재귀 구현처럼 중복된 계산이 잦은 경우 함수 호출 오버헤드와 스택 증가로 인해 성능 이슈와 스택 오버플로우 위험이 크다.
신중한 선택: 재귀는 편리한 도구이지만 모든 문제에 만능은 아니다. 가독성이 중요한 계층 구조에는 재귀를, 성능이 중요한 단순 반복 계산에는 반복문을 사용하는 등 상황에 맞춰 신중하게 선택해야 한다.