C/C++ 재귀(Recursion)

개요

하나의 함수에서 함수 자기 자신을 호출함으로써 로직을 구현하는 기법을 "재귀"라고 하며, 이 재귀를 사용하는 함수를 재귀 함수라고 한다. 주로 반복적인 작업을 하며, 같은 함수에 인자를 순차적으로 다르게 줌으로써(내림차순 등등) 반복적인 작업을 루프를 복잡하게 사용하지 않고 처리할 수 있을 때, 자주 사용한다. 반복 작업이란 특성으로 인해, 루프로 변환할 수도 있는 경우가 있다.

재귀 함수의 종류

1. 꼬리 재귀

    void func(int n)
    {
        if (n > 0)
        {
            printf("%d", n);  // ascending
            func(n - 1);
        }
    }
   

   함수를 다른 처리를 모두 끝낸 후, 마지막에 호출하는 방식을 꼬리 재귀라고 한다. 처리를 한 뒤에 함수를 호출하기 때문에 부가적인 처리가 호출 타임에 실행된다. 함수는 호출과 함수의 작동을 완료한 후, 리턴 타임으로 분류된다. 이 때, 꼬리 재귀는 호출 타임에 다른 작업을 처리하는 것이다.

   꼬리 재귀의 중요한 특성으로, 쉽게 루프로 변환할 수 있다. 함수 자리에 변수를 넣고 루프로 바꿈으로써 쉽게 변환할 수 있다.

2. 머리 재귀

    void func(int t)
    {
        if (n > 0)
        {
            func(n - 1);
            prinf("%d", n);
        }
    }
   

   꼬리 재귀와 반대로 함수의 호출이 일어난 뒤에, 부가적인 처리를 하는 것이다. 이 때문에 부가적인 처리는 함수가 리턴된 후인 리턴 타임에 처리가 된다. 리턴 타임에 순차적으로 처리되기 때문에 마지막으로 호출한 가장 높은 순위의 함수의 작업부터 순서대로 아래로(descending) 처리되는 특징을 가지고 있다.

3. 트리 재귀

    void func(int t)
    {
        if (n > 0)
        {
            prinf("%d", n);
            func(n - 1);
            func(n - 1);
        }
    }
   

   재귀 함수를 두 번 이상 호출하는 것이다. 이 것이 트리 재귀인 이유는, 재귀를 분석할 때, 사용하는 트리를 보면 알 수 있다. 함수를 여러 번 호출 했기 때문에 각각의 함수 호출마다 또 아래의 재귀 호출이 존재하고, 하나의 함수에서 함수 호출 트리가 마치 가지처럼 뻗어나가게 된다.

4. 중첩 재귀

    void fun1(int n)
    {
        if (n > 100)
        {
                return n - 10;
        } else
        {
            return fun1(fun1(n + 11));
        }
    }
   

   재귀 함수의 인자로 함수의 리턴 값을 사용하는 방식이다. 인자의 함수의 호출이 끝나야 인자로 감싸고 있는 함수의 호출이 시작되는 방식이다.

재귀를 이용한 함수 코딩

1. 팩토리얼(factorial)

    #include <stdio.h>
   
    int fact(int n)
    {
     if(n==0)
         return 1;
     return fact(n-1)*n;
    }
   
    int Ifact(int n)
    {
     int f=1,i;
     for(i=1;i<=n;i++)
         f=f*i;
   
     return f;
    }
   

   fact함수는 재귀를, Ifact는 루프를 사용한다. 단순한 곱이나 합이 존재할 때는 리턴에 바로 함수를 호출하는 방식을 쓴다. n! = n* (n-1)* (n-2)* (n-3)*... 임을 활용하여, 반복적인 곱을 n * fact(n-1)으로 표현한다. n! 당 n번의 곱이 이루어지기 때문에 시간 복잡도 면에서 O(n)이다.

2. 파워 시리즈

    #include <stdio.h>
   
    int pow(int m, int n)
    {
        if (n == 0)
        {
            return 1;
        } else if (n % 2 == 0)
        {
            return pow((m * m), n / 2);
        }
        else
        {
            return m * pow((m * m), (n - 1) / 2);
        }
    }
   

3. 테일러 시리즈

    #include <stdio.h>
   
    double e(int x, int n)
    {
     static double p=1,f=1;
     double r;
   
     if(n==0)
         return 1;
     r=e(x,n-1);
     p=p*x;
     f=f*n;
     return r+p/f;
    }
    int main()
    {
     printf("%lf \n",e(4,15));
     return 0;
    }
   

   머리 재귀 방식에서 함수 호출 후에 부가적인 처리를 넣은 경우, 리턴 타임에 가장 최근의 함수의 작동부터 처리되는 descending 방식을 이용하여, n이 0일 때부터 순차적으로, x^n와 n!의 값을 1부터 누적해 나감으로써 테일러 급수를 표현한다, static 정적인 변수를 사용함으로써 함수를 반복 호출할 때마다 값이 사라지지 않고, 누적되는 결과를 얻어낸다. 하지만, 시간 복잡도 면에서 O(n^2)의 비효율적인 처리가 일어남으로 다음의 방식으로 더 효율적으로 코딩한다.

    ouble e(int x, int n)
    {
     static double s = 1;
     if(n==0)
         return s;
     s=1+x*s/n;
     return e(x,n-1);
    }
   

   테일러 급수에 분배 법칙을 사용해 공통항을 묶어 냄으로써 Horner's Rule을 사용해 곱과 덧셈의 반복(재귀)으로 표현할 수 있다. 자세한 사항은 인터넷 검색

   정적인 결과 s에 일정한 로직으로 순차적으로 값을 누적해 나가며 꼬리 재귀를 이용해 이 때는 가장 처음 호출한 함수부터 값을 처리해 나간다. 리턴 값에 함수 호출을 하며, 이 함수의 리턴 값은 n==0일 때까지 미뤄진다. 그로 인해, 모든 값 누적이 완료 되었을 때, return s를 함으로써, 결과 s가 끝까지 전달되는 신기한 로직을 사용한다.

4. 피보나치 수열

    #include <stdio.h>
   
    int fib(int n)
    {
     int t0=0,t1=1,s=0,i;
   
     if(n<=1) 
        return n;
   
     for(i=2;i<=n;i++)
     {
     s=t0+t1;
     t0=t1;
     t1=s;
     }
   
     return s;
    }
    int rfib(int n)
    {
     if(n<=1)
         return n;
     return rfib(n-2)+rfib(n-1);
    }
   
    int F[10];
    int mfib(int n)
    {
     if(n<=1)
     {
         F[n]=n;
         return n;
     }
     else
     {
         if(F[n-2]==-1)
             F[n-2]=mfib(n-2);
         if(F[n-1]==-1)
             F[n-1]=mfib(n-1);
             F[n]=F[n-2]+F[n-1];
         return F[n-2]+F[n-1];
     }
    }
   

   fib함수는 루프를 통해, rfib는 재귀 함수를 통해 피보나치 수열을 구현한다. 재귀 함수 구현을 보면, 일반적인 피보나치 수열의 정의인 f(n) = f(n-1) + f(n-2)를 이용함을 알 수 있다. 구현이 매우 간단한지만, 시간 복잡도 면에서 O(2^n)의 비용이 소모되며 매우 비효율적임을 알 수 있다. 이는 피보나치 수열의 각각 값을 구하기 위해 반복적으로 재귀함수를 호출하고, 그 결과, 같은 인자를 가진 함수가 여러 번 호출되는 과다 호출이 일어나기 때문이다. 이를 해결하기 위해 피보나치 수열의 값이 구해지면, 배열에 저장함으로써 해당 수열 값이 필요할 때, 꺼내서 사용하여 같은 함수 호출을 없애는 memorization을 사용한다. 이를 구현한 것이 mfib 함수이며 값은 F(n) 배열에 저장한다.