재귀함수

9. 재귀적 용법  재귀적 용법은 수학에서 무한한 값을 유한하게 표현하기 위한 재귀적 수식으로부터 유래한 것으로서 의미와 표현방법에 있어서 동일하다. 예를 들면 수학에서 양의 정수를 모두 표현할 수 없으나, 재귀적 함수식을 사용하면 값을 모두 정의할 수 있다.            n=0  ⇒  f(n)=0          n=1  ⇒  f(n)=1          n>1  ⇒  f(n)=f(n-1)+1   재귀적 함수식을 사용하는 또 다른 예로 n에 대한 factorial 값은 다음과 같이 재귀적으로 정의할 수 있다.            n=0  ⇒  fac(n)=1          n=1  ⇒  fac(n)=1          n>1  ⇒  fac(n)=n * fac(n-1)     재귀적 표현을 그대로 프로그래밍 언어로 표현한 것이 소위 재귀적 함수(recursive function)이다.   프로그래밍 언어에서 재귀적 함수는 두 가지 방법으로 관찰된다.     - 함수 안에서 자기 자신의 함수를 직접 호출하는 방법   - 두개의 함수가 상호간 호출하는 방법     재귀적 용법은 함수에만 국한되지 않고, 자료형에도 적용된다. 즉 구조체(레코드)에서 데이터 항목이 자신과 동일한 구조체형으로 정의되는 경우를 자료형의 재귀적 용법이라고 한다.   1.9.1  재귀적 함수 함수의 호출은 일반적으로 호출문의 위치에 피호출 함수의 명령코드가 복사되는 것으로 이해되지만 실제에 있어서 함수의 호출은 실행순서를 피호출함수에 넘겨주고, 피호출함수의 실행이 끝나면 호출함수의 원위치로 제어순서를 되돌려 준다. 따라서 함수의 호출은 호출당시의 프로그램 상태(state)를 보존하고, 경우에 따라서는 자료의 일부를 피호출 함수에 전달하고, 피호출 함수의 종료와 더불어 호출 함수의 원상태를 회복하여 다음 과정을 올바르게 진행시킬 수 있어야 한다.       따라서 재귀적 함수는 호출할 때마다 자료상태의 보존과 함수의 종료와 더불어 호출 당시의 상태를 회복하여 호출함수로 복귀하는 문제들이 모색되어야 한다. 이에 관련 재귀적 함수의 호출과 실행에 대한 문제는 LIFO(Last-in First-out)의 개념으로 운영되는 스택(stack)을 이용하여 늦게 호출된 함수부분이 일찍 호출된 함수보다 먼저 종료되도록 관리되어야 한다. 따라서 재귀적 함수는 제어순서의 변경과 자료상태 보존과 원상태의 회복 및 호출함수의 복귀를 위한 실행 알고리즘을 별도로 운영해야 한다.         factorial 프로그램을 통하여 재귀적 함수의 실행과정을 살펴보자.   #include <stdio.h> int fac(int n) {    if (n<1)            res=1;       else            res=n*fac(n-1);       printf("%d, ", res);  /* print_2 */ }   main(void)  {     fac(3);         printf("end of program"); /* print_1 */  }   위 프로그램은 main() 함수가 종료될 때까지 아래 그림 9.1-2와 같은 순서로 fac()을 반복해서 호출한다. 이때 printf()는 함수의 상태에 따라 fac(1), fac(2), fac(3), main() 순으로 실행되어 1, 2, 6, end of program를 출력시킨다.      재귀적 함수는 반복문에 의한 함수(iterative function)보다 스택 메모리로 인하여 기억장소의 사용이 증가하고 알고리즘으로 실행시간이 증가하기 때문에 효율성이 떨어진다. 그러나 프로그램의 이해를 향상시키고 프로그램의 우아한 형식을 필요로 하거나, 반복문으로 프로그램 작성이 어려울 경우에는 재귀적 함수를 작성하는 것이 좋다.   따라서 다음 두 경우에는 재귀적 함수 대신에 반복문(iterative statement)으로 작성하는 것이 효율적이다.   1) 재귀적 함수 호출문이 함수에서 마지막 명령문인 경우.      좌측 재귀적 함수는 우측처럼 반복문 while 또는 do-while 문으로 간단히  서술될 수 있다.     1)   sub()                             sub()         {    if (i>j)                     {    while (i>j)              {    i++;      ===>                 i++;                    sub();                }              }                                 }     2)  sub()                               sub()        {     i++;                           {    do               if (i>j)        ===>                i++;                   sub();                         while (i>j);        }                                     }   2) 재귀적 함수의 호출이 스택을 기하급수적으로 증가시키는 경우 예를 들어 피보나치의 수열을 구하는 함수를 재귀적 함수로 작성해 보면, 스택의 크기가 기하급수적으로 성장하는 것을 관찰할 수 있다. 피보나치 수열은 n=0일 때 fib(n)=0, n=1일 때 fib(n)=1이라면, n>1인 경우에 피보나치 수는 fib(n)=fib(n-1)+fib(n-2)로 정의된다. 즉 n번째 피보나치 수는 (n-1)번째와 (n-2)번째 피보나치 수를 찾아야 되므로 자신의 함수가 두 번 호출되어야 한다. 이것은 곧 재귀적 함수를 관리하는데 필요한 스택을 기하급수적으로 증가시키는 요인이 된다. 따라서 이와 같은 경우에는 함수를 반복문으로 작성하는 것이 실행시간과 메모리 사용에 있어서 효율적이다.   재귀적 함수( 반복적 함수     int fib(int i)    {    if (i==0)              return (0);         else         if (i==1)              return (1);         else             return (fib(i-1)+fib(i-2));    }      int fib(int i)      {     int f=1, u=0, s=0;            while (i > 0)            {    s=f+u;                  u=f; f=s;                  i=i-1;            }            return (s);     }  피보나치 수를 구하는 함수      /* n-factorial 구하는 함수 fac() */ double fac(int n) {    if (n<=1)              return(1);       else             return(n * fac(n-1)); }      /* p와 q의 최대공약수 구하는 함수 gcm() */ int gcm(int p, int q)    {     int r;        r=p%q;        if (r!=0)              return(gcm(q, r));        else               return(q); }       /* 입력문자 역출력 함수 invert() */ invert( int i)   {     char *q;        if (i>=0)       {      scanf("%c", q);               invert(--i);       }      else               return(0);      printf("%2c", *q ); }