재귀함수 - 하노이 타워

하노이 타워 문제란 A, B, C의 기둥이 있을 때 A의 모든 원반을 C로 옮기는 문제이다.

단, 원반은 한번에 하나씩 옮길 수 있고 작은 원반 위에 큰 원반이 올려져서는 안된다.

이걸 어떻게 재귀적으로 구현하냐면.. 규칙을 찾아보자. 원반은 1, 2, 3, 4로 크기를 구분하도록 하자

만약 원반이 3개가 있다고 가정했을 때 

A의 세개의 원반을 C로 옮기기 위해선 원반 3을 C로 옮겨야 함. 그리고 이를 위해선 원반 1과 2를 먼저 원반 B로 옮겨야 한다.

만약 원반이 4개가 있다고 가정하면

A의 네개의 원반을 C로 옮기기 위해선 원반 4를 C로 옮겨야 함. 그리고 이를 위해선 원반 1과 2와 3을 먼저 원반 B로 옮겨야 한다.

그렇다면 규칙이 원반 N개를 A에서 C로 옮길 때

1. 작은 원반 N-1개를 A에서 B로 옮기고

2. 큰 원반을 A에서 C로 옮기고

3. 다시 작은 원반 N-1개를 B에서 C로 옮긴다

그럼 이걸 코드로 구현하면 다음과 같다 

#include <stdio.h>

void HanoiTowerMove(int num, char fr, char by, char to){

if(num==1){

printf("원반1 %c에서 %c로 이동 \n", fr, to);

}

else{   

HanoiTowerMove(num-1, fr, to, by);

printf("원반%d %c에서 %c로 이동 \n", num, fr, to);

HanoiTowerMove(num-1, by, fr, to); 

}

}

int main(void){

HanoiTowerMove(5, 'A', 'B', 'C');

return 0;

}