문제 풀이

하노이의 탑은 재귀 호출로 해결할 수 있는 대표적인 문제입니다. 이 문제를 반복문이나 다른 방식으로 해결하려고 한다면 굉장히 어렵게 느껴집니다. 하지만 재귀를 이용한다면 아주 직관적이고 간단하게 해결할 수 있습니다.

재귀는 부분 문제들을 동일한 로직을 이용하여 처리하기 때문에 단순하고 반복적인 작업에 적용할 수 있습니다. 하노이의 탑 문제도 원판 하나를 하나의 기둥에서 다른 기둥으로 옮기는 것을 반복하는 단순한 문제이기 때문에 재귀를 적용할 수 있습니다. 재귀를 이용하여 이 문제를 어떻게 해결할 수 있을지 살펴봅시다.

재귀 정의

앞서 살펴본 대로 다음 단계를 따라 재귀를 정의해보겠습니다.

1. 상태

2. 종료 조건

3. 점화식