Page 166 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

순차곱셈 구하기

재귀의 사용 예로 가장 먼저 살펴볼 문제는 음이 아닌 정수의 순차곱셈(factorial)을 구하는
프로그램입니다. 음이 아닌 정수 n의 순차곱셈 (n!)은 아래처럼 재귀적으로 정의할 수 있습
니다.

1. 0! = 1
2. n > 0이면 n! = n ×(n – 1)!

예컨대 10의 순차곱셈인 10!은 10 × 9!로 구할 수 있고 그 우변에서 사용되는 식 9!은 9 × 8!
로 구할 수 있습니다. 위의 정의를 그대로 프로그램으로 구현하면 실습 5-1의 factorial 함수
와 같습니다.

실습 5-1 •완성 파일 chap05/factorial.c
01 /* 순차곱셈의 결과를 재귀적으로 구합니다. */ 실행 결과
02 #include <stdio.h>
정수를 입력하세요：3
03
3의 순차곱셈 값은 6입니다.
04 /*--- 정수 n의 순차곱셈 값을 반환 ---*/
05 int factorial(int n)
06 {
07 if(n > 0)
08 return n * factorial(n – 1);
09 else
10 return 1;
11 }
12 int main(void)
13 {
14 int x;
15 printf("정수를 입력하세요. : ");
16 scanf("%d", &x);
17 printf("%d의 순차곱셈 값은 %d입니다.\n", x, factorial(x));
18
19 return 0;
20 }

factorial 함수는 매개변수 n에 전달받은 값이 0보다 크면 n * factorial(n – 1)을 반환하고, 그
렇지 않으면 1을 반환합니다.

166 C 알고리즘