재귀 함수 기본

기본 패턴

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

설명

재귀는 문제를 더 작은 같은 종류의 문제로 나누어 푸는 함수 설계 방식입니다.
가장 중요한 요소는 더 이상 자기 자신을 호출하지 않고 끝나는 base case입니다.
재귀는 수학적 정의와 구조적으로 닮아 있어 트리, 분할 정복, 백트래킹 설명에 자주 등장합니다.
반복문으로 바꿀 수 있는 문제도 많으므로, 가독성과 스택 사용량을 함께 비교해야 합니다.

짧은 예제

#include <stdio.h>

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main(void) {
    printf("%d\n", factorial(5));
    return 0;
}

빠른 정리

항목	설명
base case	재귀를 멈추는 종료 조건
recursive case	더 작은 문제로 자기 자신을 다시 호출
호출 스택	각 호출 상태가 스택에 쌓임
장점	구조가 분명한 문제를 짧게 표현 가능
단점	깊은 호출은 스택 사용량이 커짐

주의할 점

종료 조건이 잘못되면 무한 재귀로 스택 오버플로우가 발생할 수 있습니다. 재귀는 항상 "어떻게 줄어드는가"와 "언제 끝나는가"를 먼저 확인해야 합니다.