[DS] Factorial (팩토리얼)

# 팩토리얼

- 팩토리얼이란?

  >  n이 하나의 자연수일 때, 1에서 n까지의 모든 자연수의 곱을 n에 상대하여 이르는 말

 

 

# 반복문으로 팩토리얼 구현하기

[코드]

#include<stdio.h>

void factorial(int n);

int main() {
	factorial(20);
}

void factorial(int n) {
	int i, j;
	int total;

	for (i = 2; i <= n; i++) {
		total = 1;
		for (j = 2; j <= i; j++) {
			total = total * j;
		}
		printf("%d! = %d\n", i, total);
	}
}

 

[실행결과]

팩토리얼1 실행결과

 

- 실행결과를 보면 12!까지는 정상적으로 계산이되지만 13!부터는 계산이 틀림

- 이유: 계산 결과 값이 저장되는 total 변수의 자료형이 정수형(int)dlamfh chleo 2,147,483,647 (4)바이트 까지만 저장 가능하기 때문. 이러한 현상을 오버플로우라고 부름

* 오버플로우의 해결방법: 더 큰 자료형 사용하기

 

 

 

# 재귀호출로 팩토리얼 구현하기

 - n! = 1 // 초기 값 where n = 0

 - n! = n*(n-1)! // where n >= 1

 

[코드]

#include <stdio.h>

long GetFactorial(int n);

int main() {
    printf("factorial of %d is %ld\n",8,GetFactorial(8));
    return 0;
}

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

 

> main 함수에서 GetFactorial(5)를 호출하면 매개 변수 n은

0이 아니므로 else 블록에서 n*GetFactorial(n-1)이 실행됨

> 또 다른 GetFactorial 함수가 실행되고 인자 4가 전달됨

> 이를 그림으로 정리하면 다음과 같음

 

재귀 함수의 호출 과정

> n이 0에 도달하면 if 블록이 실행되어 1이 반환되면서 더 이상 함수가 호출되지 않음

> n==0이 되는 조건을 종결 조건이라고 함

 

[실행결과]

팩토리얼2 실행결과