팩토리얼 계산하기

 

 

 

팩토리얼은 느낌표로 자연수 뒤에 느낌표를 붙이는 것으로써 표현합니다.

n! 은 1부터 n까지의 자연수를 모두 곱한 것입니다.

 

 

예를 들어

5! = 1 x 2 x 3 x 4 x 5 = 120이고 3! = 1 x 2 x 3 = 6입니다

 

 

factorial(int n)이라는 함수를 만들고 싶습니다.

그렇다면 이 함수를 어떻게 작성해야 할까요?

 

알고리즘을 생각해봅시다.

일단 반복문을 사용해서 시작해볼까나~~

 

1에서부터 숫자를 n까지 증가시켜서 하나의 변수에 모두 곱합니다.

 

int factorial(int n)
{
    int temp = 1;
    
    for(int i = 2; i <= n; i++)
    {
    	temp = temp*i;
    }
    return temp;
}

 

 

<재귀적으로 팩토리얼을 계산하는 법>

1! = 1

n! = n x (n - 1)!이다. (n>1)

 이것이 자기 자신을 이용하여 재귀적으로 표현하는 방법입니다.

 

예를 들어 4! 을 풀어써보면 

 

4! = 4 x (4-1)! = 4x3!

= 4 x 3 x 2!

= 4 x 3 x 2 x 1!

= 4 x 3 x 2 x 1

 

그럼 이제 n! 을 재귀적으로 구하는 함수를 작성 해 봅시다!

 

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

여기서 한 발짝 더 나아가 봅시다.

 

만약 if(n == 1) { return 1;}이라는 종료 조건이 없다면 어떤 일이 생길까요?

 

정답은 댓글로 적어주세요!

 

그렇다면 실험을 해봅시다.

 

n = 1000000 일 때 , factorial(n)의 값은 어떻게 될까요?

 

 

 

 

factorial(1000000)을 계산한 값

 

 

 

 

왜 이런 일이 벌어질까요?

 

그것은 1000000! 이 int 타입의 범위를 훨씬 넘기 때문입니다.

int	-2,147,483,648 ~ 2,147,438,647

그럼 이를 해결해 보도록 할까욧!
출발~

 

 

 

결괏값이 int형의 범위를 넘어가는지 체크하고 만약 int형의 범위를 넘어간다면 int형의 범위를 넘어간다는 메시지를 띄워 주면 됩니다.

 

int factorial(int n)
{
    int temp = 1;
    
    for(int i = 2; i <= n; i++)
    {
    	temp = temp*i;
    }
    if(temp > Integer.MAX_VALUE)
    {
    	System.out.println("err")
    	// 자바 version -- System.out.println("err");
        // c언어 version-- printf("err\n");
        
        return -1;
    }
    return temp;
}

 

그럼 newFactorial(1000000)은 어떻게 될까요?

 

 

 

 

stack overflow error

 

 

 

 

위의 에러 구문과 같이 stackOverflowError가 나옵니다.

 

이는 newFactorial()이 재귀 호출하면서 메모리의 스택을 계속 누적해서 사용하다가 스택이 부족하여 스택 오버플로우가 발생하기 때문입니다.

 

그래서 재귀적으로 프로그램을 작성할 때, 큰 입력에 대해 재귀 호출이 계속 일어나서 스택 오버플로우가 발생하는 경우를 조심해야 합니다.

 

--------------------------------------------------------------------------------------------------------

 

이처럼 재귀 호출로 작성한 프로그램은 모두 재귀 호출을 사용하지 않는 형태로 바꿀 수 있습니다.

 

하지만 재귀 호출을 이용하면 프로그램이 간결하고 쉬워집니다.

 

앞으로 복잡해 보이는 문제를 재귀적 프로그래밍으로 쉽게 해결하는 경우를 많이 찾아볼 수 있을 것입니다.
(코드가 짧아지는데 솔직히 점화식 세우기가 힘듭니다)