[C언어] 재귀적 팩토리얼 구현

■ 팩토리얼 구현

C언어로 재귀(순환, recursion)적 팩토리얼을 구현하면 다음과 같다. 

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

 

결과값을 볼 수 있는 전체 실행코드

#include <stdio.h>

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

int main()
{
	int a = factorial(3);
	printf("%d ", a);
}

3을 입력하면, factorial(3)이 실행된다. factorial(3)이 실행되는 도중에 factorial(2)를 호출하고, factorial(2)은 factorial(1)를 호출한다. factorial(1)은 매개 변수 n이 1이므로 if문장에서 참이 되어 1를 리턴한다. 이 반환값 1은 factorial(2)로 전달되고, factorial(2)는 여기에 2를 곱한 값인 를 factorial(3)으로 전달한다. 

결국 아래 과정과 같다. 

factorial(3) = 3*factorial(2) = 3*2*factorial(1) = 3*2*1 = 6

 

■ 순환 호출의 내부적인 구현

순환을 이해하기 위해서는 함수 호출 과정을 알아야 한다. 함수가 자기 자신(함수)를 호출하면 다른 함수를 호출하는 것과 같이 '복귀주소'를 시스템 스택에 저장한다. 이어서 호출되는 함수를 위한 매개변수와 지역 변수를 스택으로부터 할당받는다. 이렇게 함수를 위한 시스템 스택에서의 공간을 활성 레코드(activation record)라고 한다. 호출된 함수가 끝나게 되면 시스템 스택에서 복귀주소를 추출하여 호출한 함수로 되돌아가게 된다. 순환 호출이 계속 중첩될수록 시스템 스택에는 활성 레코드들이 쌓이게 된다.