재귀함수

재귀함수 ( recusive function)란 함수의 실행부 내에서 그 자신을 호출하는 함수를 말한다.

프로그램 내의 반복문은 재귀호출로 바꿀 수 있으며 그 역으로 재귀호출은 반복문으로 고쳐 쓸 수 있다.

다음의 예제를 통해 재귀함수를 알아 보자

#include <stdio.h>

void recursive_print(int);


int main ()
{
       int num;

       printf ( "enter a positive integer:");
       scanf("%d",&num);
       recursive_print(num);

       return 0;
}



void recursive_print( int n)
{
        if (n <=0) return;

        else
        {
             printf("recursive_print: n = %d\n",n);
             recursive_print(n-1);
         }

}

프로그램에서 recursive_print() 함수는 실행부에서 스스로를 호출한다.

재귀함수의 기본적인 형태는 if -else 문이다. if절에서는 종료 조건을 명시하고 함수의 실행을 종료시킨다. else절에서는 반복해서 재귀호출을 시도한다. 재귀호출의 인수를 변경하여 마지막에 재귀호출이 종료되게 한다.

재귀 호출은 반복문으로 작성할 수 있으며, 반복문도 재귀호출로 작성할 수 있다. 제어변수의 초기화, 반복 여부를 결정하는 조건식, 제어변수 값의 변경으로 구성할 수 있다.

재귀함수 부분을 반복문으로 만들어 보자

void print_loop( int n)
{
       while ( n >0 )
       {
           printf("loop_print:n = %d\n",n);
           n = n -1;
        }
}

재귀호출에서 제어변수는 형식인수가 실인수의 값을 넘겨받을 때 초기화가 이루어진다. while 문에서는 실행이 시작되기 이전에 초기화 되어야 한다.

재귀호출 에서는 if절에서  반복여부가 명시되고, 반복문에서는 while문의 조건식으로 명시 되었다.

재귀함수는 재귀호출의 인수를 변경하여 제어변수를 변경하였고, 반복문에서는 실행부내에서 제어변수를 결정한다.

재귀함수의 예로 많이 사용되는 factorial을 계산하는 예제를 보자

4! = 4 * 3* 2* 1

4! = 4 * 3! = 4 * (4-1)!

이런식이 된다.

다음의 예제를 보자

#include <stdio.h>

int factorial (int n);

int main()
{

   int num, nfact;
   printf(" enter a integer: ");
   scanf("%d",&num);
   nfact = factorial (num);
   printf("factorial of %d is %d\n",num, nfact);

   return 0;
}


int factorial(int n)
{
       if(n <= 1) return(1);
       else
       {
           printf("%d * factorial(%d)\n",n,n-1);
           return (n * factorial (n-1));
       }
}