상태

하노이의 탑에서 제시된 문제는 원판 n개를 기둥 1에서 기둥 3으로 옮기는 과정입니다. 여기에서 문제를 정의하는 총 3개의 변수를 잡을 수 있습니다.

1. 옮기려는 원판의 개수 n

2. 원판이 현재 위치한 기둥 from

3. 원판이 이동해야 하는 기둥 to

이렇게 3개의 변수가 상태를 구성합니다. 따라서 하노이의 탑 문제에서 상태는 (n, from, to)로 잡을 수 있습니다. 이렇게 할 경우 제시된 문제인 원판 n개를 기둥 1에서 기둥 3으로 옮기는 과정은 (n, 1, 3)으로 나타낼 수 있습니다. 따라서 하노이의 탑 문제의 재귀 상태는 다음과 같이 정의됩니다.

(n, from, to) = 원판 n개를 기둥 from에서 기둥 to로 옮기는 과정

종료 조건

하노이의 탑 문제에서 가장 작은 부분 문제는 원판을 고민 없이 바로 옮길 수 있는 ‘원판을 1개만 옮길 때’가 됩니다. 이 경우 추가적인 부분 문제없이 바로 원판을 원하는 기둥으로 옮길 수 있습니다. 이는 다음과 같이 표현할 수 있습니다.