생초보가 c언어 하노이탑 재귀호출 질문드립니다.
글쓴이: vltfhem / 작성시간: 토, 2014/05/03 - 7:47오후
#include
void hanoi(int n, int src, int dest);
void main()
{
int num;
printf("Enter the number of Hanoi Tower : ");
scanf("%d", &num);
hanoi(num, 1, 3);
}
void hanoi(int n, int src, int dest)
{
static int count=0;
int middle=6-src-dest;
if (n>1)
hanoi(n-1, src, middle);
printf("%d : disk %d %d->%d\n", ++count, n, src, dest);
if (n>1)
hanoi(n-1, middle, dest);
}
위와 같은 프로그램인데
재 짧은 생각으로는
첫번째로 실행되는
if (n>1)
hanoi(n-1, src, middle);
에서 n이 1이 되어 printf를 실행하고 아래의if문을 실행하지 않고 프로그램이 종료될거라 예상하였지만 그렇지 않더군요..
위 재귀호출이 어떻게 돌아가는지 설명 도움을 주실분이 계신지요 ㅠ
Forums:
가장 간단한 방법
출력 함수를 이용한 원시 디버깅
void hanoi(int n, int src, int dest) { static int count=0; int middle=6-src-dest; printf("Hanoi(%d, %d, %d) 호출\n", n, src, dest); if (n>1) { printf("Hanoi(%d, %d, %d)의 첫 번째 Hanoi(%d, %d, %d)가 호출됩니다.\n", n, src, dest, n-1, src, middle); hanoi(n-1, src, middle); } printf("%d : disk %d %d->%d\n", ++count, n, src, dest); if (n>1) { printf("Hanoi(%d, %d, %d)의 두 번째 Hanoi(%d, %d, %d)가 호출됩니다.\n", n, src, dest, n-1, middle, dest); hanoi(n-1, middle, dest); } } ============== 결과 (input: 5) Hanoi(5, 1, 3) 호출 Hanoi(5, 1, 3)의 첫 번째 Hanoi(4, 1, 2)가 호출됩니다. Hanoi(4, 1, 2) 호출 Hanoi(4, 1, 2)의 첫 번째 Hanoi(3, 1, 3)가 호출됩니다. Hanoi(3, 1, 3) 호출 Hanoi(3, 1, 3)의 첫 번째 Hanoi(2, 1, 2)가 호출됩니다. Hanoi(2, 1, 2) 호출 Hanoi(2, 1, 2)의 첫 번째 Hanoi(1, 1, 3)가 호출됩니다. Hanoi(1, 1, 3) 호출 1 : disk 1 1->3 2 : disk 2 1->2 Hanoi(2, 1, 2)의 두 번째 Hanoi(1, 3, 2)가 호출됩니다. Hanoi(1, 3, 2) 호출 3 : disk 1 3->2 4 : disk 3 1->3 Hanoi(3, 1, 3)의 두 번째 Hanoi(2, 2, 3)가 호출됩니다. Hanoi(2, 2, 3) 호출 Hanoi(2, 2, 3)의 첫 번째 Hanoi(1, 2, 1)가 호출됩니다. Hanoi(1, 2, 1) 호출 5 : disk 1 2->1 6 : disk 2 2->3 Hanoi(2, 2, 3)의 두 번째 Hanoi(1, 1, 3)가 호출됩니다. Hanoi(1, 1, 3) 호출 7 : disk 1 1->3 8 : disk 4 1->2 Hanoi(4, 1, 2)의 두 번째 Hanoi(3, 3, 2)가 호출됩니다. Hanoi(3, 3, 2) 호출 Hanoi(3, 3, 2)의 첫 번째 Hanoi(2, 3, 1)가 호출됩니다. Hanoi(2, 3, 1) 호출 Hanoi(2, 3, 1)의 첫 번째 Hanoi(1, 3, 2)가 호출됩니다. Hanoi(1, 3, 2) 호출 9 : disk 1 3->2 10 : disk 2 3->1 Hanoi(2, 3, 1)의 두 번째 Hanoi(1, 2, 1)가 호출됩니다. Hanoi(1, 2, 1) 호출 11 : disk 1 2->1 12 : disk 3 3->2 Hanoi(3, 3, 2)의 두 번째 Hanoi(2, 1, 2)가 호출됩니다. Hanoi(2, 1, 2) 호출 Hanoi(2, 1, 2)의 첫 번째 Hanoi(1, 1, 3)가 호출됩니다. Hanoi(1, 1, 3) 호출 13 : disk 1 1->3 14 : disk 2 1->2 Hanoi(2, 1, 2)의 두 번째 Hanoi(1, 3, 2)가 호출됩니다. Hanoi(1, 3, 2) 호출 15 : disk 1 3->2 16 : disk 5 1->3 Hanoi(5, 1, 3)의 두 번째 Hanoi(4, 2, 3)가 호출됩니다. Hanoi(4, 2, 3) 호출 Hanoi(4, 2, 3)의 첫 번째 Hanoi(3, 2, 1)가 호출됩니다. Hanoi(3, 2, 1) 호출 Hanoi(3, 2, 1)의 첫 번째 Hanoi(2, 2, 3)가 호출됩니다. Hanoi(2, 2, 3) 호출 Hanoi(2, 2, 3)의 첫 번째 Hanoi(1, 2, 1)가 호출됩니다. Hanoi(1, 2, 1) 호출 17 : disk 1 2->1 18 : disk 2 2->3 Hanoi(2, 2, 3)의 두 번째 Hanoi(1, 1, 3)가 호출됩니다. Hanoi(1, 1, 3) 호출 19 : disk 1 1->3 20 : disk 3 2->1 Hanoi(3, 2, 1)의 두 번째 Hanoi(2, 3, 1)가 호출됩니다. Hanoi(2, 3, 1) 호출 Hanoi(2, 3, 1)의 첫 번째 Hanoi(1, 3, 2)가 호출됩니다. Hanoi(1, 3, 2) 호출 21 : disk 1 3->2 22 : disk 2 3->1 Hanoi(2, 3, 1)의 두 번째 Hanoi(1, 2, 1)가 호출됩니다. Hanoi(1, 2, 1) 호출 23 : disk 1 2->1 24 : disk 4 2->3 Hanoi(4, 2, 3)의 두 번째 Hanoi(3, 1, 3)가 호출됩니다. Hanoi(3, 1, 3) 호출 Hanoi(3, 1, 3)의 첫 번째 Hanoi(2, 1, 2)가 호출됩니다. Hanoi(2, 1, 2) 호출 Hanoi(2, 1, 2)의 첫 번째 Hanoi(1, 1, 3)가 호출됩니다. Hanoi(1, 1, 3) 호출 25 : disk 1 1->3 26 : disk 2 1->2 Hanoi(2, 1, 2)의 두 번째 Hanoi(1, 3, 2)가 호출됩니다. Hanoi(1, 3, 2) 호출 27 : disk 1 3->2 28 : disk 3 1->3 Hanoi(3, 1, 3)의 두 번째 Hanoi(2, 2, 3)가 호출됩니다. Hanoi(2, 2, 3) 호출 Hanoi(2, 2, 3)의 첫 번째 Hanoi(1, 2, 1)가 호출됩니다. Hanoi(1, 2, 1) 호출 29 : disk 1 2->1 30 : disk 2 2->3 Hanoi(2, 2, 3)의 두 번째 Hanoi(1, 1, 3)가 호출됩니다. Hanoi(1, 1, 3) 호출 31 : disk 1 1->3저는 이렇게 생각했습니다.
댓글 달기