[C/C++] 팩토리얼 구현하기 (재귀함수의 이해)

팩토리얼 구현

팩토리얼은 특정 값에서 1까지를 모두 곱하는 연산을 의미함.

예를 들어 10!이면 10 팩토리얼이라고 읽는 데, 10*9*8*7*.....*2*1까지 모두 곱한 연산을 하게 됨.

그렇다면 가장 기본적으로는 손쉽게 for문을 통해 이 값을 구할 수 있음

 

팩토리얼 for문 구현

부가적인 것 다 제외하면 아래 내용이 핵심임. 단순하게 1부터 a까지 곱하는 것임.

int factorial(int a)
{
	int res=1;
    
    if (a==0) return 1;
    else {
		for (int i=1; i<=a; i++)
		{
			res*=i;
		}
    }
	return res;
}

 

팩토리얼 재귀함수 구현

팩토리얼 재귀함수는 아래와 같이 구할 수 있음.

재귀함수는 항상 탈출 조건을 만들어 줘야함.

if (a==0 || a==1) return 1;로 탈출 조건 설정하면 됨. 통상 재귀함수는 이렇게 if 조건과 return 값으로 표현해서 탈출 조건을 만듦.

 

그리고 return 값으로 현재 값 곱하기 현재 값에서 1만큼 작은 팩토리얼 값을 곱하여 리턴함.

int factorial(int a)
{
	if (a==0 || a==1) return 1;
	return a*factorial(a-1);
}

이러면 어떻게 되냐면, return a*factorial(a-1);에서 팩토리얼이 다시 불리면서 팩토리얼 함수 연산이 됨. 아래와 같은 구조임. 그리고 탈출 조건인 0이나 1에서 멈추게 될 것임.

 

잘 따지고 보면 아래와 같음.

팩토리얼 계산

유의해야할 점은 return할 때 실제로는 a*factorial 함수 형태이기 때문에 return보다도 계속해서 factorial 함수를 호출해서 빠져 들어가는 구조임. 이를, 탈출 조건 만날 때까지 함.

그래서 실제 return 및 숫자 연산은 탈출 조건 만나고 지금까지 불러온 팩토리얼 함수를 하나씩 빠져나오면서 연산됨. 그전까지는 계속 함수만 재귀적으로 부르고 있는 것임. 조건 제대로 설정 안하면 탈출 조건 못 만나고 계속 factorial만 부르다가 무한 루프 빠지게 됨. if와 return으로 제대로 설정하자.