empty = 6 – from – to

따라서 첫 번째 단계는 (n–1, from, empty)로 나타낼 수 있습니다.

두 번째 단계는 하나의 원판을 from 기둥에서 to 기둥으로 옮기는 것입니다. 이는 간단히 (1, from, to)로 나타낼 수 있습니다.

마지막 세 번째 단계는 n–1개의 원판을 empty에서 to로 옮기는 것으로, (n–1, empty, to)로 나타낼 수 있습니다.

세 단계의 상태들은 모두 원판이 옮겨지는 과정을 나타냅니다. 따라서 원래 부분 문제 (n, from, to)는 각 단계를 모두 수행하는 과정이 되며, 다음과 같이 표기할 수 있습니다.

(n, from, to) = (n–1, from, empty) + (1, from, to) + (n–1, empty, to)
단 empty = 6 – from – to

따라서 재귀는 다음과 같이 정의됩니다.

▼ 표 5-3 하노이의 탑 문제의 재귀 정의