C 재귀(Recursion) 예제 #1 - 팩토리얼(Factorial)

unsigned integer인 n을 scanf로 입력받고(#define _CRT_SECURE_NO_WARNINGS 사용) n!(팩토리얼 n)의 값을 출력하는 프로그램을 재귀함수를 사용하여 작성하라.

 

 

 

예시:

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int factorial(int); //재귀함수 정의, 정의할 때 매개변수는 자료형 

int main()
{
	int num = 0;
	printf("정수 n을 입력: ");
	scanf("%d", &num); // 5를 입력했을때...
	if (num < 0) { //음의 정수를 입력했을때
		printf("0보다 큰 정수를 입력하세요.");
		return -1; //error
	}
	printf("%d! = %d\n", num, factorial(num));
	return 0;
}

int factorial(int n) //재귀함수 선언
{
	if (n == 0) { //탈출 조건(Base Case)
		return 1; // 0! = 1이고 아래 6.참조
	}
	return n * factorial(n - 1); //재귀 호출
}

 

입력: 5

<<재귀 호출 과정 (Stack 프레임이 쌓이는 순서)>> //Stack의 처리순서는 LIFO(후입선출)이다.
① factorial(5) = 5 × factorial(4)
② factorial(4) = 4 × factorial(3)
③ factorial(3) = 3 × factorial(2)
④ factorial(2) = 2 × factorial(1)
⑤ factorial(1) = 1 × factorial(0)
⑥ factorial(0) = 1 (Base case)

<<Base case 도달 후, 반환값을 계산하며 재귀 함수 종료>>
① factorial(1) = 1 × 1 = 1
② factorial(2) = 2 × 1 = 2
③ factorial(3) = 3 × 2 = 6
④ factorial(4) = 4 × 6 = 24
⑤ factorial(5) = 5 × 24 = 120

재귀 호출은 Stack 프레임을 사용하여 진행되며 가장 마지막 호출된 함수부터 차례로 종료되면서 값이 계산된다.

 

지적 환영합니다. 댓글로 고견 부탁드립니다.

유익했다면 포스트 좌하단의 ♡공감 꾹 눌러주시면 글쓴이에게 힘이 됩니다!