[C++ & C, 하노이 타워, 하노이 탑] 재귀문으로 푸는 하노이탑

하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다.

게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.

1. 한 번에 하나의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어서는 안 된다

예를 들어 n이 3이라면,

1. 기둥 A의 원반을 기둥 C으로 옮긴다.
2. 기둥 A의 원반을 기둥 B으로 옮긴다.
3. 기둥 C의 원반을 기둥 B으로 옮긴다.
4. 기둥 A의 원반을 기둥 C으로 옮긴다.
5. 기둥 B의 원반을 기둥 A으로 옮긴다.
6. 기둥 B의 원반을 기둥 C으로 옮긴다.
7. 기둥 A의 원반을 기둥 C으로 옮긴다.

이를 알고리즘으로 나눠서 계산해보면

1. 기둥 1에서 n - 1개의 원반을 기둥 2으로 옮긴다.
2. 기둥 1에서 1개의 원반을 기둥 3으로 옮긴다.
3. 기둥 2에서 n-1개의 원반을 기둥 3으로 옮긴다.
4. 반복

---

재귀문으로 풀기

int hanoi(int n, char from, char temp, char to){
	if(n == 1){
    	printf("원반 %d를 기둥 %c에서 기둥 %c으로 옮긴다.\n", n, from, to);
    }else{
    	hanoi(n-1, from, to, temp);
        printf("원반 %d를 기둥 %c에서 기둥 %c으로 옮긴다.\n", n, from, to);
        hanoi(n-1, temp, from, to);
    }
}