[백준/C언어] 10872번 - 팩토리얼

백준 웹사이트 "10872번 - 팩토리얼" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

10872번: 팩토리얼

---

소스 코드

#include <stdio.h>

int factorial(int n);

int main(void){
    int N;
    scanf("%d", &N);
    printf("%d\n", factorial(N));
}

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

---

문제 풀이

  재귀함수(recursive function)를 이용하는 가장 기본적인 문제입니다. 재귀함수는 함수를 정의할 때 자신을 재참조하는 함수입니다. 소스 코드 Line 11 ~ 16의 'factorial' 함수가 이에 해당되는데, factorial 함수의 정의 내 Line 15에서 자기 자신인 factorial 함수가 재참조되는 것을 확인할 수 있습니다. 물론, 파라미터로 n이 입력되었을 때, 다시 factorial(n)을 호출하지는 않습니다 (만약 그러면 무한루프를 돌게 되겠죠). n이 입력되면 factorial(n-1)을 호출하기 때문에, 재귀를 반복할 때마다 파라미터의 값은 1씩 줄어들게 됩니다. 파라미터의 값이 1씩 줄어들다가, 언제가는 멈춰야게죠? 그래서 마련해주는 것이 재귀함수의 '탈출 조건'인데, 예제에서의 탈출 조건은 Line 12 ~ 13으로, n이 0일 때 1을 반환함으로써 재귀를 종료합니다.

  지금까지의 설명을 정리하자면, 재귀함수를 이루기 위한 조건은 두 가지가 있습니다. 이는 Recursive Case (재귀 케이스)와 Base Case (기본 케이스)인데, 전자는 함수가 재귀를 할 조건이고, 후자는 재귀를 탈출할 조건입니다. 이 문제에서 Recursive Case는 n이 0보다 클 경우이며, Base Case는 n이 0일 경우입니다. 이렇게 되면, N이 입력되었을 때 N*factorial(N-1)이 호출되고, 이렇게 호출된 factorial(N-1)은 (N-1)*factorial(N-2)를 호출하므로 N*(N-1)*factorial(N-2)가 되고... 이렇게 반복되다가 최종적으로 N*(N-1)*...*2*1*1이 반환됩니다. 즉 Recursive Case를 반복하다가 N이 1이 되면 Base Case에 의해 재귀가 종료되며, 그때까지 쌓인 반환값들을 계산하여 반환하는 셈입니다.