Chapter 02. 함수의 재귀적 호출의 이해

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

재귀함수는 자료구조나 알고리즘의 어려운 문제를 단순화하는데 사용되는 중요한 무기입니다. 무엇보다도 재귀함수가 있기에 재귀적인 수학적 수식을 그대로 코드로 옮길 수 있습니다. 그럼 이러한 재귀함수의 특징을 보이기 위해서 팩토리얼(factorial)값을 반환하는 함수를 재귀적으로 구현해 보겠습니다.

//main.c 소스 파일로 저장
#include <stdio.h>

int Factorial(int num)
{
	if (num > 2) num *= Factorial(num - 1);

	return num;
}

int main(void)
{
	int facNum = 5;
	printf("Factorial %d : %d\n",facNum, Factorial(facNum));

	return 0;
}

/*
실행결과

Factorial 5 : 120

*/

재귀 함수를 구현하는 것은 저도 생각을 조금 하게 만듭니다. 위 예제는 책에 있는 것이 아닌 제가 직접 구현해 본 것입니다. 이 책에서 구현한 예제는 다음과 같습니다.

//main.c 소스 파일로 저장
#include <stdio.h>

int Factorial(int num)
{
	if(num == 0) return 1;
	else return num * Factorial(num - 1);
}

int main(void)
{
	printf("1! = %d\n", Factorial(1));
   	printf("2! = %d\n", Factorial(2));
	printf("3! = %d\n", Factorial(3));
	printf("4! = %d\n", Factorial(4));
	printf("9! = %d\n", Factorial(9));

	return 0;
}

/*
실행결과

1! = 1
2! = 2
3! = 6
4! = 24
9! = 362880

*/

제가 직접 구현한 예제와 이 책의 예제를 비교한 이유는 다음과 같습니다. 우선 이 책에서 구현한 Factorial 함수를 보면 불필요한 함수 호출을 2번 하고 있습니다. 매개변수로 1이 주어질 때와 0이 주어질 때입니다. 하지만 제가 구현한 함수는 매개변수로 2가 주어질 때가 마지막 호출이 됩니다.

 

함수의 호출과정은 다소 시간이 걸리는 것으로 알고 있습니다. 그래서 기왕이면 함수를 덜 호출하는 쪽이 좋습니다. 뭐, 해봐야 2회 차이기 때문에 별 차이는 없을 것입니다. 하지만 이런 부분까지 고려해서 저는 함수를 호출하는 부분에 조건문을 달았습니다.

 

제가 구현한 Factorial 함수는 num가 일정 값 이상이면 여기에 1을 때서 다시 함수를 호출합니다. 그러다 num가 조건문에 맞지 않으면 인자로 받은 num를 그대로 반환합니다. 이 때 num로 입력한 값이 2인 경우까지는 그대로 반환해도 문제가 없습니다. 그래서 조건문으로 num가 2보다 클 것을 요구했습니다.