Recursion vs. Iteration : Round 2

부제 : 컴퓨터조차 세상의 끝을 보기가 쉽지 않아.

하노이 탑

19세기경 유럽에서는 "창세기부터 지금까지 브라마 사원에서 계속되고 있다"는 선전용 문구와 함께 유명했던 "하노이 탑"이라는 게임이 있었다.

전설에 의하면 아직도 계속되고 있다는 이 게임은 창세기에 그 사원의 사제가 하나님으로부터 다이아몬드로 된 세 개의 말뚝에 꽂혀 있는 구리 제단을 받았는데, 첫 번째 말뚝에는 금으로 된 64개의 원반이 쌓여 있었고, 각 원반은 바로 밑에 있는 원반보다 조금씩 작았다. 사제는 모든 원반을 두 번째 말뚝을 이용하여 세 번째 말뚝에 옮기는 임무를 부여 받았는데, 다음과 같은 규칙이 있었다.

1. 원반은 한번에 하나씩만 옮겨야 한다. 결국 가장 작은 맨 위의 원반만 옮길 수 있다.
2. 위에 놓인 원반은 아래의 원반보다 클 수 없다.

만일 그 사제가 64개의 원반을 옮기는 작업을 다 끝내면, 이 세상에는 종말이 온다고 한다.

(위 내용은 'C로 배우는 프로그래밍 기초'에서 일부 발췌했음을 알려드립니다)

지난 주에
재귀가 반복보다 더 나은 경우를 찾아오겠다고 대뜸 선언해버리고
찾아도 찾아도 안나오길래 한 며칠간 머리좀 싸맸지요

그러다 이것(하노이)과 멱(거듭제곱)을 구하는 케이스를 찾아내었는데
아무래도 이걸 올리는게 좋을 것 같다는 생각을 했습니다

피보나치 수열과 더불어 프로그래밍을 배우는 사람이라면 한번은 보고 지나가게 되는 내용입니다

재귀로 구현한 것과 같은 알고리즘을 사용하기가 다소 난해하여
반복으로 구현한 것을 자주 볼 일은 없겠지만 이것도 반복으로 구현이 가능합니다

먼저 재귀부터 보시죠

int trial = 0; void Hanoi_Recursive( unsigned n, char from, char mid, char to ) { if( n == 1 ) { trial++; printf( "%5d: 원반 %d을 말뚝 %c에서 말뚝 %c로 이동\n", trial, 1, from, to ); } else { Hanoi_Recursive( n-1, from, to, mid ); trial++; printf( "%5d: 원반 %d을 말뚝 %c에서 말뚝 %c로 이동\n", trial, n, from, to ); Hanoi_Recursive( n-1, mid, from, to ); } }

역시 재귀가 알고리즘 자체는 매우 간단하지 않습니까?

간단히 설명을 하자면
원반이 1개일 때는 시작 축에서 끝 축으로 옮기기만 하면 됩니다

원반의 개수가 n개가 되면
일단 n-1개의 원반을 시작 축에서 중간 축으로 몰아놓고,
n번째 원반을 끝 축으로 옮긴 뒤 남은 n-1개의 원반을 끝 축으로 옮기면 되겠죠

이번에도 input에 따른 실행시간을 보겠습니다

input n에 대해서 2^n -1번의 시행을 출력하기 때문에
input의 증가에 따른 시간의 증가가 눈에 띄게 증가함을 알 수 있습니다

반복으로 구현한 것을 보시죠

void Hanoi_Iterative( unsigned n, char from, char mid, char to ) { if( n == 1 ) { printf( "%5d: 원반 %d을 말뚝 %c에서 말뚝 %c로 이동\n", 1, 1, from, to ); } else { int i, j, exp; for( i = 1; i < pow( 2, n ); i++ ) { for( j = 1; j <= n; j++ ) { exp = (int)pow( 2, j ); if( i%exp == exp/2 ) { switch( ( i%( 3*exp ) )/exp ) { case 0: if( j%2 ^ n%2 ) printf( "%5d: 원반 %d을 말뚝 %c에서 말뚝 %c로 이동\n", i, j, from, mid ); else printf( "%5d: 원반 %d을 말뚝 %c에서 말뚝 %c로 이동\n", i, j, from, to ); break; case 1: if( j%2 ^ n%2 ) printf( "%5d: 원반 %d을 말뚝 %c에서 말뚝 %c로 이동\n", i, j, mid, to ); else printf( "%5d: 원반 %d을 말뚝 %c에서 말뚝 %c로 이동\n", i, j, to, mid ); break; case 2: if( j%2 ^ n%2 ) printf( "%5d: 원반 %d을 말뚝 %c에서 말뚝 %c로 이동\n", i, j, to, from ); else printf( "%5d: 원반 %d을 말뚝 %c에서 말뚝 %c로 이동\n", i, j, mid, from ); break; } } } } } }

ㅋㅋㅋㅋㅋㅋㅋㅋ 조금 복잡하죠?

이 알고리즘에 대해 간단히(?) 설명을 하자면.. 아래의 컬러박스를 보시면 됩니다
컬러박스 하단에 설명을 해놓았으나, 이해가 안되시면
컬러박스 상단에 써놓은 진행을 보고 대충 이렇게 되는구나 하고 넘어가시면 됩니다

n = 3
0: 123 x x (시작)
1: 23 x 1  (원반1 이동)
2: 3 2 1    (원반2 이동)
3: 3 12 x  (원반1 이동)
4: x 12 3  (원반3 이동)
5: 1 2 3    (원반1 이동)
6: 1 x 23  (원반2 이동)
7: x x 123 (원반1 이동, 끝)
--------
n = 4
 0: 1234 x x (시작)
 1: 234 1 x  (원반1 이동)
 2: 34 1 2    (원반2 이동)
 3: 34 x 12   (원반1 이동)
 4: 4 3 12    (원반3 이동)
 5: 14 3 2    (원반1 이동)
 6: 14 23 x   (원반2 이동)
 7: 4 123 x   (원반1 이동)
 8: x 123 4   (원반4 이동)
 9: x 23 14   (원반1 이동)
10: 2 3 14    (원반2 이동)
11: 12 3 4    (원반1 이동)
12: 12 x 34  (원반3 이동)
13: 2 1 34    (원반1 이동)
14: x 1 234  (원반2 이동)
15: x x 1234 (원반1 이동, 끝)
--------
두 경우를 각각 보시면
원반1은 시행수를 2로 나눈 나머지가 1일 때 이동하고,
원반2는 시행수를 4로 나눈 나머지가 2일 때 이동하고,
원반3은 시행수를 8로 나눈 나머지가 4일 때 이동하고
모든 원반이 이것을 만족하므로 for문을 중첩시켜서 돌리면 적당하겠지요

이동경로의 경우
n이 홀수이면
　홀수번의 원반은 '시작 축 → 끝 축 → 중간 축 → 시작 축'을 반복하고,
　짝수번의 원반은 '시작 축 → 중간 축 → 끝 축 → 시작 축'을 반복합니다
n이 짝수이면
　홀수번의 원반은 '시작 축 → 중간 축 → 끝 축 → 시작 축'을 반복하고,
　짝수번의 원반은 '시작 축 → 끝 축 → 중간 축 → 시작 축'을 반복합니다
모든 원반이 이것을 만족하고, 이동경로의 경우 3회마다 반복되므로
원반1을 예로 들면
　'시행수를 6(=3×2)으로 나눈 나머지'를 2로 나눈 몫이 0이면 1회째 이동을 하고,
　'시행수를 6(=3×2)으로 나눈 나머지'를 2로 나눈 몫이 1이면 2회째 이동을 하고,
　'시행수를 6(=3×2)으로 나눈 나머지'를 2로 나눈 몫이 2이면 3회째 이동을 합니다
나머지가 0인 경우를 skip하기 위해 if문을 중첩하고, 3회의 이동을 처리하기 위해 switch를 사용하였습니다

피보나치 때는 반복이 더 빠를 것 같다는 것을 비교적 쉽게 짐작할 수 있었는데 이건 잘 모르겠죠?
별 수 없이 프로그램을 돌려서 시간을 재는 수 밖에는 없을 것 같네요

.. 미세하지만 재귀가 빠르군요;

사실 이건 한두번 돌리고 찍은 스샷들이라 오차가 있을 수 있으며
실제 실행시 반복으로 구현한 쪽이 조금 더 빠르게 나올 수 도 있습니다

.. 만,

이걸 한번 보시겠습니까?

!?

위의 두 스샷과는 비교도 안될만큼 빠르지 않습니까?
input을 입력하고 실행창을 작업표시줄로 내려버리면 나타나는 결과인데.. 원인을 전혀 모르겠습니다?
(혹시나 해서 피보나치에도 해봤는데 거기엔 안되더군요 -_-;)

원인을 아시는 분은 담당파트와 관계없이 포스팅좀.. 굽신굽신


마지막 스샷까지 참고하면 이번엔 명백한 재귀의 승리인가요 ㅋ

다음번에는
지난 주의 피보나치에서 실행속도가 너무 느리던 재귀함수를 개량해보도록 하겠습니다 (__)

(포스팅 소요시간 : 약 150분)