C 언어 재귀 함수(Recursive Function) 쉽게 이해하기 – 팩토리얼 예제로 배우는 재귀 호출

재귀 함수(Recursive Function)란 어떤 것을 자기 자신으로 정의하는 방식을 말하며, 함수 본문 안에서 스스로를 다시 호출하는 함수를 의미합니다.

재귀 함수의 기본 개념

재귀의 대표적인 예시는 정수 N의 팩토리얼(factorial)을 계산하는 fact() 함수입니다. 팩토리얼은 1부터 N까지의 모든 자연수를 곱한 값입니다.

이 함수는 인자가 0 또는 1로 호출되면 1을 반환하고, 그 외의 경우에는 n * fact(n-1)을 반환합니다. 이 과정은 n이 1이 될 때까지 반복됩니다.

fact(5)의 실행 과정

Fact(5) = 5 * fact(4)
        = 5 * 4 * fact(3)
        = 5 * 4 * 3 * fact(2)
        = 5 * 4 * 3 * 2 * fact(1)
        = 5 * 4 * 3 * 2 * 1
        = 120

위 과정에서 볼 수 있듯이, 재귀 호출은 문제를 점점 작은 단위로 나누어 가다가 종료 조건(n == 1 또는 n == 0)에 도달하면 결과를 거꾸로 되돌아오며 계산합니다.

C 언어 재귀 함수 예제 코드

다음은 재귀 함수를 사용해 팩토리얼을 구하는 C 프로그램입니다.

#include<stdio.h>
int main() {
    int n, f;
    int fact(int);
    printf("enter a number");
    scanf("%d", &n);
    f = fact(n);
    printf("factorial value = %d", f);
}
int fact(int n) {
    int f;
    if ((n == 1) || (n == 0))
        return 1;
    else
        f = n * fact(n - 1);
    return f;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

Enter a number 5
Factorial value = 120

재귀 함수 사용 시 주의할 점

재귀 함수를 작성할 때는 반드시 종료 조건(base case)을 명확히 설정해야 합니다. 종료 조건이 없으면 함수가 무한히 자기 자신을 호출하여 스택 오버플로우(stack overflow)가 발생할 수 있습니다. 또한 깊은 재귀 호출은 성능 저하를 일으킬 수 있으므로, 간단한 반복문으로 해결 가능한 경우라면 반복문 사용을 고려하는 것이 좋습니다.