(1, from, to) = [[from, to]]

이 조건을 살펴보면 원판 개수인 n에 1이 고정되어 있고, 기둥인 from과 to는 변수 상태 그대로입니다. 따라서 원판 개수가 1이며, 기둥 위치는 상관없는 조건이 됩니다. 따라서 “원판 1개를 from에서 to로 옮기는 부분 문제”는 바로 ‘from에서 to로 원판을 옮기면 된다’는 의미가 됩니다.

점화식

이제 상태를 가장 작은 상태로 전이시켜 줄 점화식을 세워야 합니다. 점화식을 간단히 찾을 수 있으면 좋겠지만 찾기 힘든 문제가 많습니다. 이때는 제시된 문제를 해결할 수 있는 가장 큰 상태와 종료 조건에서 찾은 가장 작은 상태를 이용하여 유추해볼 수 있습니다.

제시된 문제를 나타내는 상태는 (n, from, to)이며 종료 조건에서 찾은 가장 작은 상태는 (1, from, to)입니다. n 변수가 1로 수렴하려면 n 값이 점점 줄어들어야 함을 알 수 있습니다. 따라서 상태 변수 n이 n–1로 전이되어야 한다고 가정해보고 이를 이용하여 부분 문제를 해결할 수 있는 점화식을 세울 수 있을지 살펴봅시다. 즉, (n, from, to)를 나타내는 부분 문제를 (n–1, from, to)를 이용하여 풀 수 있는지 확인해야 합니다.

종료 조건에서는 n 값이 1인 것만 포함됩니다. 기둥 위치인 from과 to는 조건에 포함되지 않으므로 굳이 하나의 부분 문제와 여기에서 전이된 또 다른 부분 문제가 같은 기둥을 사용할 필요는 없습니다. 따라서 우리 가정은 다음과 같습니다.