icon안동민 개발노트

재귀 함수

재귀 함수 개요

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

 이는 복잡한 문제를 더 작고 관리하기 쉬운 하위 문제로 나누어 해결하는 방법을 제공합니다.

 재귀는 많은 알고리즘과 자료 구조에서 중요한 역할을 하며, 특히 트리와 그래프 관련 문제에서 자주 사용됩니다.

재귀 함수의 기본 구조

 재귀 함수는 일반적으로 다음과 같은 구조를 가집니다.

return_type recursive_function(parameters) {
    if (base_case) {
        return base_result;
    } else {
        // 문제를 더 작은 문제로 나누고 자기 자신을 호출
        return recursive_function(modified_parameters);
    }
}

 여기서 알아야 할 중요한 두 가지는 기저 조건과, 재귀 단계입니다.

 1. 기저 조건 (Base case) : 재귀 호출을 멈추는 조건

 2. 재귀 단계 (Recursive step) : 문제를 더 작은 문제로 나누는 단계

재귀 예시 : 팩토리얼 계산

 팩토리얼은 재귀 함수의 고전적인 예입니다.

#include <iostream>
 
int factorial(int n) {
    if (n <= 1) return 1;  // 기저 조건
    return n * factorial(n - 1);  // 재귀 단계
}
 
int main() {
    std::cout << "5! = " << factorial(5) << std::endl;  // 출력: 5! = 120
    return 0;
}

재귀 함수의 작동 원리

 재귀 함수가 호출될 때마다 새로운 스택 프레임이 생성됩니다. 이 스택 프레임은 지역 변수와 반환 주소를 저장합니다.

 예를 들어, factorial(5)를 호출하면 다음과 같은 과정이 발생합니다.

  1. factorial(5) 호출 → 5 * factorial(4) 반환
  2. factorial(4) 호출 → 4 * factorial(3) 반환
  3. factorial(3) 호출 → 3 * factorial(2) 반환
  4. factorial(2) 호출 → 2 * factorial(1) 반환
  5. factorial(1) 호출 → 1 반환 (기저 조건)

 그 후 역순으로 결과가 계산됩니다. 1 * 2 * 3 * 4 * 5 = 120

재귀 vs 반복

 동일한 문제를 재귀와 반복 두 가지 방식으로 해결할 수 있습니다.

 예를 들어서 피보나치 수열을 계산하는 함수를 살펴봅시다.

#include <iostream>
 
// 재귀 버전
int fibonacci_recursive(int n) {
    if (n <= 1) return n;
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}
 
// 반복 버전
int fibonacci_iterative(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}
 
int main() {
    int n = 10;
    std::cout << "Fibonacci(" << n << ") recursive: " << fibonacci_recursive(n) << std::endl;
    std::cout << "Fibonacci(" << n << ") iterative: " << fibonacci_iterative(n) << std::endl;
    return 0;
}

 재귀 버전은 코드가 더 간결하고 문제의 정의에 더 가깝지만, 반복 버전은 일반적으로 메모리 사용이 더 효율적입니다.

재귀 함수의 장단점

 장점

  • 복잡한 문제를 간단하게 표현 가능
  • 코드의 가독성 향상
  • 일부 알고리즘에서 자연스러운 구현 (예 : 트리 순회)

 단점

  • 메모리 사용량 증가 (스택 오버플로우 위험)
  • 함수 호출 오버헤드로 인한 성능 저하 가능성
  • 디버깅이 어려울 수 있음

꼬리 재귀 (Tail Recursion)

 꼬리 재귀는 재귀 호출이 함수의 마지막 연산인 특별한 형태의 재귀입니다.

 이는 컴파일러 최적화를 통해 반복문처럼 효율적으로 실행될 수 있습니다.

int factorial_tail(int n, int accumulator = 1) {
    if (n <= 1) return accumulator;
    return factorial_tail(n - 1, n * accumulator);
}

 많은 현대 컴파일러는 꼬리 재귀 최적화를 지원하여, 이러한 형태의 재귀를 반복문으로 변환합니다.

재귀 함수의 응용

  1. 정렬 알고리즘 : 퀵 소트, 머지 소트
  2. 트리 순회 : 전위, 중위, 후위 순회
  3. 그래프 탐색 : DFS (깊이 우선 탐색)
  4. 동적 프로그래밍 : 메모이제이션을 통한 최적화
예시 : 이진 트리의 중위 순회
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
 
void inorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    inorderTraversal(root->left);
    std::cout << root->val << " ";
    inorderTraversal(root->right);
}

연습 문제

  1. 문자열이 회문(palindrome)인지 확인하는 재귀 함수를 작성하세요.
  2. 주어진 정수의 각 자릿수 합을 계산하는 재귀 함수를 작성하세요.
  3. n번째 피보나치 수를 계산하는 재귀 함수를 작성하고, 메모이제이션을 사용하여 최적화하세요.

 참고자료

  • "Introduction to Algorithms" by Thomas H. Cormen et al. (Chapter 4 : Divide-and-Conquer)
  • "The Art of Computer Programming, Vol. 1" by Donald E. Knuth (Section 1.2.1 : Mathematical Induction)
  • "Thinking Recursively with Java" by Eric Roberts
  • C++ Core Guidelines의 함수 관련 규칙 : F : Functions
  • "Recursive Programming" article on Stanford CS Education Library : Link
이전으로다음으로