하노이 타워

 대학교 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)로 이동'이 된다.