재귀(Recursion)

4.3 재귀(Recursion)

함수가 자기 자신을 호출하는 기법입니다:

4.3.1 재귀의 기본 개념

#include <iostream>

// 재귀적으로 팩토리얼 계산
int factorial(int n) {
    // 기저 조건(base case): 재귀를 종료하는 조건
    if (n <= 1) {
        return 1;
    }
    
    // 재귀 호출: 더 작은 문제로 분할
    return n * factorial(n - 1);
}

int main() {
    int num = 5;
    std::cout << num << "! = " << factorial(num) << std::endl;  // 5! = 120
    
    return 0;
}

재귀의 주요 요소:

1. 기저 조건(Base Case): 재귀를 종료하는 조건
2. 재귀 호출(Recursive Call): 자기 자신을 호출하되, 더 작은 문제로 분할
3. 재귀 과정(Recursive Process): 나중에 호출된 함수가 먼저 완료되어 역순으로 결과 계산

재귀의 작동 원리 시각화 (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)))
= 5 * (4 * (3 * 2))
= 5 * (4 * 6)
= 5 * 24
= 120

4.3.2 재귀 예제

피보나치 수열(Fibonacci Sequence)

#include <iostream>

// 재귀적으로 피보나치 수 계산
int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    std::cout << "피보나치 수열: ";
    for (int i = 0; i < 10; i++) {
        std::cout << fibonacci(i) << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

하노이 탑(Tower of Hanoi)

#include <iostream>

// 원판 이동 과정 출력
void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        std::cout << "원판 1을 " << from << "에서 " << to << "로 이동" << std::endl;
        return;
    }
    
    hanoi(n - 1, from, aux, to);
    std::cout << "원판 " << n << "을 " << from << "에서 " << to << "로 이동" << std::endl;
    hanoi(n - 1, aux, to, from);
}

int main() {
    int numDisks = 3;
    hanoi(numDisks, 'A', 'C', 'B');
    
    return 0;
}

이진 탐색(Binary Search)

#include <iostream>
#include <vector>

// 재귀적 이진 탐색
int binarySearch(const std::vector<int>& arr, int target, int left, int right) {
    if (left > right) {
        return -1;  // 찾지 못함
    }
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) {
        return mid;  // 찾음
    } else if (arr[mid] > target) {
        return binarySearch(arr, target, left, mid - 1);  // 왼쪽 절반 탐색
    } else {
        return binarySearch(arr, target, mid + 1, right);  // 오른쪽 절반 탐색
    }
}

int main() {
    std::vector<int> sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int target = 14;
    
    int index = binarySearch(sortedArray, target, 0, sortedArray.size() - 1);
    
    if (index != -1) {
        std::cout << target << "은(는) 인덱스 " << index << "에 있습니다." << std::endl;
    } else {
        std::cout << target << "을(를) 찾을 수 없습니다." << std::endl;
    }
    
    return 0;
}

4.3.3 꼬리 재귀(Tail Recursion)

함수의 마지막 연산이 재귀 호출인 최적화 형태입니다:

#include <iostream>

// 일반 재귀 팩토리얼
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // 재귀 호출 후 곱셈 연산
}

// 꼬리 재귀 팩토리얼
int tailFactorial(int n, int accumulator = 1) {
    if (n <= 1) return accumulator;
    return tailFactorial(n - 1, n * accumulator);  // 마지막 연산이 재귀 호출
}

int main() {
    std::cout << "일반 재귀: " << factorial(5) << std::endl;
    std::cout << "꼬리 재귀: " << tailFactorial(5) << std::endl;
    
    return 0;
}

꼬리 재귀의 장점:

• 컴파일러 최적화 가능 (스택 프레임 재사용)
• 스택 오버플로우 위험 감소
• 반복문으로 자동 변환 가능

4.3.4 재귀의 한계와 최적화

#include <iostream>
#include <unordered_map>

// 단순 재귀 피보나치 (비효율적)
int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);  // 중복 계산 발생
}

// 메모이제이션 적용 피보나치
int memoizedFib(int n, std::unordered_map<int, int>& memo) {
    // 이미 계산된 결과가 있는지 확인
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    
    // 기저 조건
    if (n <= 1) {
        return n;
    }
    
    // 결과 계산 및 저장
    memo[n] = memoizedFib(n - 1, memo) + memoizedFib(n - 2, memo);
    return memo[n];
}

int optimizedFibonacci(int n) {
    std::unordered_map<int, int> memo;
    return memoizedFib(n, memo);
}

int main() {
    int n = 40;
    
    // 시간 측정
    auto start = std::chrono::high_resolution_clock::now();
    std::cout << "최적화된 피보나치(" << n << ") = " << optimizedFibonacci(n) << std::endl;
    auto end = std::chrono::high_resolution_clock::now();
    
    std::chrono::duration<double> elapsed = end - start;
    std::cout << "최적화 버전 실행 시간: " << elapsed.count() << "초" << std::endl;
    
    // 작은 값에서만 일반 버전 테스트 (너무 느림)
    n = 30;
    start = std::chrono::high_resolution_clock::now();
    std::cout << "일반 피보나치(" << n << ") = " << fibonacci(n) << std::endl;
    end = std::chrono::high_resolution_clock::now();
    
    elapsed = end - start;
    std::cout << "일반 버전 실행 시간: " << elapsed.count() << "초" << std::endl;
    
    return 0;
}

재귀의 한계:

• 스택 메모리 제한으로 인한 스택 오버플로우
• 중복 계산으로 인한 성능 저하
• 깊은 재귀에서의 디버깅 어려움

최적화 기법:

• 메모이제이션(Memoization): 이전 계산 결과 저장
• 꼬리 재귀 최적화
• 반복문 변환 (일부 경우)