[Algorithm] 재귀를 이용하여 하노이의 탑 해결하기

재귀( recursion )란?

어떠한 함수가 내부에서 자기 자신을 호출하는 것

 

하노이의 탑

재귀함수를 사용하여 하노이의 탑 문제를 해결하는 코드를 만들어보자.

 

Hanoi 함수는 개수가 2개일 때를 생각하고 만들면 굉장히 간단하다.

 

n 이 2일 때를 가정하면 

2번째 돌을 바닥에 깔기 위해서는 자신의 위에 있는 돌을 전부 오픈된 공간으로 보내야한다.

따라서 1번째 돌을 옮겨야 하는데 결국 첫번째 돌은 n-1 번째 돌이다. 즉 n-1번째의 돌을 _open으로 보내는 것을 먼저하고( 함수 1번째 라인)

2번째 위치를 바꾼다( 함수 2번째 라인 ) 

그리고 다시 n-1의 위치를 _dest로 옮겨야 하는데 n-1의 돌은 현재 _open 위치에 있다. 따라서 출발지점은 _open이 되며 목적지는 _dest이고 빈공간은 _start가 된다.( 함수 3번째 라인 ) 

이러한 작업이 끝나면 2층 돌은 1번칸에서 3번칸으로 전부 움직인 상태가 된다.

그림으로 그리면 편하다. 다 같이 한번 그려보자.