재귀 함수(Recursion)

김재혁·2025년 1월 22일

재귀 함수

개념

함수가 자기 자신을 호출하는 방식으로 문제를 해결하는 함수.

복잡한 문제를 단순한 부분 문제로 나누어 해결할 수 있음.

재귀 함수의 핵심은 기저 조건(Base Case)과 재귀 조건(Recursive Case).

기본 구성 요소

기저 조건(Base Case) : 재귀 호출을 종료하는 조건. 이 조건이 없으면 함수가 무한히 자기 자신을 호출하게 되어 스택 오버플로우를 일으킬 수 있음.

재귀 조건(Recursive Case) : 자기 자신을 호출하는 부분. 문제를 더 작은 부분 문제로 나누는 역할을 함.

특징

간결한 코드 : 재귀를 사용하면 반복문을 사용하는 것보다 코드를 간결하게 작성할 수 있음. 특히 트리나 그래프 탐색과 같은 문제에서 매우 유용.

문제 해결의 직관성 : 문제를 더 작은 부분 문제로 나누어 해결할 수 있어, 문제를 자연스럽게 풀 수 있음.

성능 저하 : 재귀 함수는 함수 호출 시마다 스택 메모리를 사용하기 때문에, 함수 호출이 많아지면 메모리 오버헤드가 발생할 수 있음.

스택 오버플로우 : 재귀 깊이가 너무 깊어지면 시스템의 스택 메모리를 초과해 스택 오버플로우(Stack Overflow) 오류가 발생할 수 있음.

디버깅 어려움 : 재귀는 함수 호출이 중첩되므로, 호출 스택을 추적하기 복잡할 수 있음.

예시

1. 팩토리얼 계산(n!) : n이 자연수일 때, 1~n까지의 모든 자연수의 곱.
#include <iostream>
using namespace std;
// 재귀 함수: 팩토리얼 계산
int factorial(int n) {
    if (n == 0 || n == 1) { // 기저 조건
        return 1;
    } else {
        return n * factorial(n - 1); // 재귀 조건
    }
}
기저 조건 : n==0 또는 n==1일 때, 팩토리얼 값은 1 -> 재귀 종료 조건.

재귀 조건 : n이 0 또는 1이 아닐 때, n*factorial(n-1)을 반환하며 자기 자신을 호출.

재귀 함수 동작 흐름 : Ex) factorial(5) 계산.

factorial(5)가 호출되면 5*factorial(4)를 호출.

factorial(4)가 호출되면 4*factorial(3)을 호출.

factorial(3)이 호출되면 3*factorial(2)를 호출.

factorial(2)가 호출되면 2*factorial(1)을 호출.

factorial(1)이 호출되면 기저 조건에 의해 1을 반환.

반환된 값들이 차례로 곱해져 (5, 4, 3, 2 ,1) == 120이 반환.

반복문 예시

반복문은 메모리 오버헤드가 없어 더 효율적일 수 있음.
#include <iostream>
using namespace std;
int factorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; ++i) {
        result *= i;
    }
    return result;
}
2. 피보나치 수열 계산 : 첫째 및 둘째 항이 1이면 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열.
int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}
반복문
int fibonacci(int n) {
    int a = 0, b = 1;
    for (int i = 2; i <= n; ++i) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return (n == 0) ? a : b;
}