모든 원반을 첫 번째 기둥에서 세 번째 기둥으로 옮기는 고전 퍼즐이에요. 규칙은 두 가지뿐이에요 — 한 번에 하나씩만 옮기고, 큰 원반을 작은 원반 위에 올릴 수 없어요.
하노이의 탑은 1883년 프랑스 수학자 에두아르 뤼카가 만든 퍼즐이에요. 원반 64개짜리 전설도 함께 전해지는데, 승려들이 하루에 한 개씩 옮겨도 다 옮기려면 수천억 년이 걸린다는 이야기예요 — 원반 수가 하나 늘어날 때마다 필요한 이동 횟수가 두 배 가까이 폭발적으로 늘어나기 때문이에요.
기둥을 눌러 맨 위 원반을 집고, 다른 기둥을 눌러 그 위에 내려놓아요. 목표 기둥이 비어있거나, 맨 위 원반이 지금 옮기려는 원반보다 커야 내려놓을 수 있어요.
원반이 n개일 때 이론상 최소 이동 횟수는 2ⁿ−1번이에요. 큰 원반 하나를 옮기려면 그 위의 원반들을 먼저 다른 기둥으로 몽땅 옮겨둬야 하는데, 이렇게 문제를 더 작은 같은 문제로 쪼개서 푸는 방식을 컴퓨터 프로그래밍에서는 재귀라고 불러요.