하노이 타워 : The Tower of Hanoi

하노이 타워 문제는 재귀함수의 힘을 보이는 대표적인 예로 꼽힌다.

재귀적으로 접근하지 않으면 해결이 쉽지 않은 문제이다.

하노이 타워의 조건

1. 원반은 한 번에 하나씩만 옮길 수 있다.

2. 옮기는 과정에서 작은 원반의 위에 큰 원반이 올려져서는 안된다.

하노이 타워는 원반의 수가 늘어나도 해결방법에는 차이가 없다. 다만 원반의 수가 늘어날수록 일련의 과정을 더 많이 반복해야 할 뿐이다.

그래서 그 일련의 과정을 파악하면 해결할 수 있게된다.

원반 n개를 옮기는 과정

1. 작은 원반 n-1개를 A에서 B로 이동.

2. 큰 원반 1개를 A에서 C로 이동.

3. 작은 원반 n-1개를 B에서 C로 이동.

이렇듯 원반 n개를 이동하는 문제는 원반 n-1개를 이동하는 문제로 세분화되고, 또 원반 n-1개를 이동하는 문제는 원반 n-2개를 이동하는 문제로 세분화된다.

즉, 원반 n개를 이동하는 문제는 결국 원반 1개를 이동하는 매우 쉬운 문제로 세분화되는 것이다.

재귀함수를 정의하는데 있어서 반드시 생각해야 할 것은 재귀의 탈출조건이다. 

그런데 n개의 원반 이동이 n-1개의 원반 이동으로 세분화되어서 재귀를 구성하게 된 것으므로 탈출의 조건은 다음과 같다. 

"이동해야 할 원반의 수가 1개인 경우"

코드를 보면 너무나 간단해서 허탈한 기분이 든다. 이것이 재귀의 힘...