원반 n개를 이동시키는 부분 문제는 원반 n – 1개를 이동시키는 부분 문제로 해결할 수 있다.

이렇게 적고 보니 굉장히 당연한 이야기입니다. 원반 n–1개를 이동시킬 수 있다면 맨 위 원반 n–1개는 빈 기둥에 옮기고 가장 아래 원반은 목표 기둥에 옮긴 후, 빈 기둥에 옮겨 놓았던 n–1개의 원반은 목표 기둥에 옮겨 주면 됩니다.

▲ 그림 5-6 부분 문제를 이용하여 기둥을 옮기는 과정

이것을 점화식으로 표현해봅시다. (n, from, to)를 해결하는 첫 번째 단계는 n–1개의 원판을 from이나 to가 아닌 빈 기둥으로 옮기는 것입니다. 문제에서 기둥은 각각 1, 2, 3으로 나타나므로 빈 기둥 empty는 다음과 같이 계산할 수 있습니다.