하노이 탑(The Tower of Hanoi)은 3개의 막대 중에서 막대 하나에 쌓여 있는 n개의 원판을 다른쪽 막대로 옮기는 게임이다. 단, 아래의 규칙을 지켜야 한다. 1. 한번에 하나의 원판만 이동한다. 2. 맨 위에 있는 원판만 이동한다. 3. 크기가 작은 원판위에 큰 원판을 쌓을 수 없다. n개의 원판을 옮기기 위해서는 먼저 임시 막대에 n-1개의 원판을 옮긴 후 처음 막대에 남아있는 맨 밑 원판을 목적지 막대에 옮기는 것을 반복한다. 그러고나면 원래 원판이 쌓여있던 막대는 빈 막대가 되고 임시 막대에는 n-1개의 원판이, 목적지 막대에는 가장 큰 원판이 하나 놓여있게 된다. 임시 막대에 있는 원판의 개수를 n으로 다시 설정하고 n-1개의 원판을 원래 원판이 있었던 첫막대에 옮긴다. 임시 막대에..
