2-1 함수의 재귀적 호출

 

#1 재귀 함수는 어케 생겼을까

 

여기 재귀 함수 하나가 있다.

void Recursive(void)
{
    printf("Recursive call\n");
    Recursive(); //자기 자신 호출
}

 

완료 되지 않은 함수를 다시 호출하는 것은

 

사실 함수가 호출될 때 마다 해당 함수의 복사본을 더 만들어 실행하는 구조이다.

 

함수를 구성하는 명령문은 CPU로 이동(복사)되어 실행 된다.

 

따라서 위 Recursive() 함수는 중간쯤에 있는 명령문을 실행하는 도중에

 

다시 Recursive() 함수의 명령문을 CPU 로 이동(복사)시키는 건 문제가 되지 않는다.

 

이것이 재귀적인 형태의 함수이다.

 

물론 계속 호출하면 무한 루프가 될 수 있기에 탈출 조건 만들면된다.

 

---

#2 재귀함수의 디자인 사례

 

그렇다면 재귀함수는 앞으로 문제를 해결할 때 어떻게 사용을 할까?

 

재귀함수의 특징을 보기 위해 팩토리얼(Factorial)값을 반환하는 함수를 만들어 보자

 

우선 팩토리얼의 수학적 의미는 다음과 같다

n! = n x (n - 1) x (n - 2) x (n - 3) x ······· x 2 x 1

 

정수 n의 팩토리얼은 n!으로 표시하고, 마지막은 0! 이므로 1까지 곱하게 된다.

 

이러한 팩토리얼의 재귀적 특성을 이용해 재귀 함수로 구현해보자

#include <stdio.h>

int Factorial(int n)
{
   if(n==0)
       return 1;
   else
       return n * Factorial(n-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;
}

실행해보면 각각의 팩토리얼값을 잘 나타낸다.