하노이의 탑을 풀어보자.

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

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

하노이의 탑 문제는 재귀 호출을 이용하여 풀 수 있는 가장 유명한 예제 중의 하나이다. 그렇기 때문에 프로그래밍 수업에서 알고리즘 예제로 많이 사용한다. 일반적으로 원판이 n개 일 때, 2n -1번의 이동으로 원판을 모두 옮길 수 있다.

 

이 규칙들을 이용하여 63(64)개의 원판을 다른 막대로 전부 옮기는 것은 간단해 보이지만 '작은 원반 위에 큰 원반을 올릴 수 없다' 는 규칙은 의외로 크게 작용하는데, 이를 지키면서 n개의 원반을 한쪽 기둥에서 다른 쪽으로 옮기는 데 걸리는 최소 횟수가 2^n - 12n−1번이기 때문이다.

재귀함수를 사용하면 쉽게 풀 수 있다.

n개의 원판이 있고, 3개의 기둥(시작, 보조, 목표)이 있다고 가정하자.

1. 위의 n-1개의 원판을 보조기둥으로 옮긴다.
2. n번째 원판을 목표기둥으로 옮긴다.
3. 보조기둥의 n-1개의 원판을 목표기둥으로 옮긴다.

과정은 굉장히 간단하며 이 또한 코드로 옮기면 간단하다. 이것이 재귀함수의 장점이다.

 

재귀함수를 사용할 때 팁이 있다면

바로 코딩을 하지말고 이 함수가 어떤 기능을 할지를 명확히하라.

그러고 나서 함수를 사용하면 좀 더 재귀함수를 쉽게 설계할 수 있다.

1. C코드

int Hanoi(int from, int to, int n) // from번 기둥에서 to번 기둥으로 n개의 원반을 이동.
{
    if(n == 1)
    {
        printf("%d번 기둥에서 %d번 기둥으로 이동\n", from, to);
        return 0;
    }

    Hanoi(from, 6-from-to, n-1);
    printf("%d번 기둥에서 %d번 기둥으로 이동\n", from, to);
    Hanoi(6-from-to, to, n-1);
    return 0;
}

2. 파이썬 코드

def move(current, start, end):
  if current == 0 : # 첫번째 원판이면 종료
  	return
  mid = 6 - start - end # 보조 기둥 설정
  move(current-1, start, mid) # n-1개의 원판을 시작기둥에서 보조기둥으로 이동
  print(current, end) # n번째 원판을 목표기둥으로 이동
  move(current-1, mid, end) # n-1개의 원판을 보조기둥에서 목표기둥으로 이동