#04 재귀를 이용한 팩토리얼 계산

재귀 (Recursion)

재귀(recursion)는 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻합니다. 컴퓨터 과학과 수학에서, 재귀는 함수가 자신의 정의에 의해 정의될 때의 개념을 가리킵니다.

#include <stdio.h> 
void count(int num) 
{ 
    printf("%d \\n", num); 
    count(num - 1); 
} 

int main() 
{ 
    count(5); 
    return 0; 
}

위 count() 메서드처럼 자기 자신을 호출하는 것이 재귀입니다.

재귀의 탈출 조건

위 코드를 보면 무한히 호출됩니다. 탈출 조건을 줘서 무한 반복을 끊어내야 합니다.

#include <stdio.h> 
void count(int num) 
{ 
    if (num == 0) 
        return; 
    printf("%d \\n", num); 
    count(num - 1); 
} 

int main() 
{ 
    count(5); 
    return 0; 
}

팩토리얼 (Factorial)

수학에서, 자연수의 계승 또는 팩토리얼(階乘, 문화어: 차례곱, 영어: factorial)은 그 수보다 작거나 같은 모든 양의 정수의 곱입니다. n이 하나의 자연수일 때, 1에서 n까지의 모든 자연수의 곱을 n에 상대하여 이르는 말입니다. 기호는 느낌표(!)를 쓰며 팩토리얼이라고 읽습니다.

팩토리얼의 예

• 1! = 1
• 2! = 2 * 1
• 3! = 3 * 2 * 1
• ...
• n! = n * (n-1) * (n-2) ... * 1

팩토리얼의 구현

다음은 팩토리얼을 구현하는 예제입니다.

#include <stdio.h> 

int Factorial(int num) 
{ 
    if (num < 1) 
    { 
        printf("마이너스 숫자는 입력 불가능."); 
        return 0; 
    } 

    if (num == 1) 
    { 
        printf("%d", num); 
        return 1; 
    } 
    else 
    { 
        printf("%d * ", num); 
        return num * Factorial(num - 1); 
    } 
}

int main() 
{ 
    int result = Factorial(5); 
    printf("\nresult: %d", result); 
    return 0; 
}

위 코드에서 Factorial 함수는 재귀적으로 호출되어 팩토리얼 값을 계산합니다. main 함수에서 Factorial(5)를 호출하면 5의 팩토리얼 값을 계산하는 과정을 출력합니다.

재귀의 작동 원리

재귀 함수는 기본적으로 두 가지 요소를 갖습니다:

1. 기본 조건(Base Case): 재귀 호출을 멈추기 위한 조건입니다. 이 조건이 만족되면 함수는 더 이상 자기 자신을 호출하지 않고 종료됩니다.
2. 재귀 호출(Recursive Call): 함수가 자기 자신을 호출하는 부분입니다. 문제를 조금 더 작은 버전으로 줄여서 해결합니다.

팩토리얼 재귀의 실행 순서

1. Factorial(5) 호출
2. Factorial(4) 호출
3. Factorial(3) 호출
4. Factorial(2) 호출
5. Factorial(1) 호출
6. 기본 조건에 도달하여 1 반환
7. 각 호출마다 반환된 값을 곱하여 최종 결과 계산

---

재귀 함수는 복잡한 문제를 간단하게 해결할 수 있는 강력한 도구입니다. 특히 분할 정복 알고리즘이나 트리 탐색과 같은 문제에서 유용하게 사용됩니다. 재귀의 기본 개념과 탈출 조건을 이해하고, 다양한 예제를 통해 연습하면 재귀를 활용한 문제 해결 능력을 향상시킬 수 있습니다.

직접 코드를 작성해보고 실행해 보면서 재귀 호출의 원리를 시각적으로 확인해 보세요. 이는 재귀적 사고를 기르는 데 큰 도움이 될 것입니다.