대학교 1학년 때 하노이 타워를 코딩한 기억이 있는데 다시 해보려니까 잘 되지 않았다. 그래서 코드를 참고하려고 봤는데 참고가 아니라 해석에 매진했다. 멘붕이 오는 줄 알았다.

 재귀적 표현의 시작이자 끝(?)이라 불리는 하노이 타워에 대한 코드는 아래와 같다. 직접 구현해보는게 제일 좋겠지만 어렵다면 코드를 천천히 한 번 해석하는 것도 좋을 것 같다.


#include <stdio.h>

int hanoi(int num, char first, char mid, char last)
{
    if(num==1)
    {
        printf("원반 %d을(를) %c에서 %c로 이동\n",num,first,last);
    }
    else
    {
        hanoi(num-1, first, last, mid);
        printf("원반 %d을(를) %c에서 %c로 이동\n",num,first,last);
        hanoi(num-1, mid, first, last);
    }

}

int main()
{
    hanoi(3,'A','B','C');

    return 0;
}




main에서 hanoi(3,'A','B','C')의 인자로 함수에 들어가면 hanoi(num-1, first, last, mid)을 만나고 즉, hanoi(3-1,'A','C','B')에 의해서 다시 함수에 들어간다.(first=A mid=C last=B) 이때 다시 hanoi(2-1,'A','B','C')가 호출된다.(first=A mid=B last=C) 그러면 다시 함수로 접근했을 때는 if(num==1)에 걸려서 '원반 1을 A(first)에서 C(last)로 이동'이 된다. 이제서야 hanoi(3-1,'A','C','B')에 대한 처리로 먼저 출력이 이루어진다. (first=A mid=C last=B) 다음으로 hanoi(num-1, mid, first, last)을 만나고 즉, hanoi((3-1)-1, C, A, B)가 되어 if(num==1)에 걸려서 '원반 1을 C(first)에서 B(last)로 이동'이 된다.

드디어 hanoi(3,'A','B','C')의 처리가 되어 출력된다.
그리고 num=3일때 hanoi(num-1, mid, first, last)을 다시 만난다. 즉,  hanoi(3-1, 'B', 'A', 'C')가 호출된다. (first=B mid=A last=C) 그러면 다시 함수로 접근해서 hanoi(num-1, first, last, mid)을  만나고 즉, hanoi((3-1)-1, 'B', 'C', 'A')가 되어 다시 함수에 접근할 때 if(num==1)에 걸려서 '원반 1을 B(first)에서 A(last)로 이동'이 된다. 다음으로 hanoi(3-1, 'B', 'A', 'C')의 처리가 되어 출력된다. (first=B mid=A last=C) 그리고 num=3-1일때 hanoi(num-1, mid, first, last)을 다시 만난다. 즉, hanoi((3-1)-1, 'A', 'B', 'C')가 되어 다시 함수에 접근할 때 if(num==1)에 걸려서 '원반 1을 A(first)에서 C(last)로 이동'이 된다.

 이진 탐색 알고리즘을 재귀적으로 구현해보았다.

while문으로 loop되는 부분을 고려해보면 재귀적 구현의 방법이 나온다.


#include <stdio.h>

int BinarySearch(int *arr, int first, int last, int num)
{
    int mid = (first+last)/2;
    if(arr[mid]==num)
    {
        return mid;
    }
    else
    {
        if(arr[mid] < num)
            first = mid+1;
        else
            last = mid-1;
    }

    return BinarySearch(arr,first,last,num);
}

int main()
{
    int arr[5] = {1,3,8,14,25};
    
    printf("%d\n",BinarySearch(arr,0,4,3));

    return 0;
}


 팩토리얼을 재귀 함수로 구현하였다.
일단 for문을 이용한 팩토리얼을 간단히 구현해보면 다음과 같다.


int main()
{
    int i,n=1;
    for(i=5;i>0;i--)
    {
        n=n*i;
    }
    printf("n=%d\n",n);

    return 0;
}


 이 경우 i=5이므로 5!에 대한 결과인 120을 출력한다.

이러한 반복적인 과정을 조금 생각해보면 다음과 같이 재귀적으로 구현할 수 있다.


#include <stdio.h>

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

int main()
{
    printf("%d\n", factorial(1));
    printf("%d\n", factorial(3));
    printf("%d\n", factorial(5));

    return 0;
}


+ Recent posts