[자료구조] 2장

《 재귀 호출 》

 

[ 하노이탑 문제 ]

 - 막대 A에 있는 원판들을 막대 C로 옮긴다.

 - 한 번에 한 개의 원판만 이동이 가능하다.

 - 맨 위의 원판만이 이동이 가능하다.

 - 크기가 작은 원판의 위에 크기가 큰 원판이 옮겨질 수 없다.

// C code
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

void hanoi_tower(int n, char from, char mid, char to) {

	if (n == 1) {
		printf("원반 %d(을)를 %c에서 %c로 이동\n", n, from, to);
		return;
	}
	else {
		hanoi_tower(n - 1, from, to, mid);
		printf("원반 %d(을)를 %c에서 %c로 이동\n", n, from, to);
		hanoi_tower(n - 1, mid, from, to);
	}
}

int main(void) {

	hanoi_tower(3, 'A', 'B', 'C');
	
	return 0;
}

hanoi_tower()
hanoi(3, 'A', 'B', 'C') hanoi(2, 'A', 'C', 'B') hanoi(1, 'A', 'B', 'C')	원반 1을 A → C로 이동
hanoi(2, 'A', 'C', 'B') hanoi(1, 'C', 'A', 'B')	원반 2를 A → B로 이동 원반 1을 C → B로 이동
hanoi(3, 'A', 'B', 'C') hanoi(2, 'B', 'A', 'C') hanoi(1, 'B', 'C', 'A')	원반 3을 A → C로 이동 원반 1을 B → A로 이동
hanoi(2, 'B', 'A', 'C') hanoi(1, 'A', 'B', 'C')	원반 2를 B → C로 이동 원반 1을 A → C로 이동

출력문 실행 결과