재귀함수를 통해 Tower of Hanoi (하노이의 탑)문제 해결해보자

재귀함수를 연습할 수 있는 좋은 예가 바로 하노이의 탑(Tower of Hanoi)문제이다.

하노이의 탑이란 전세계에서 인기 있는 수학 게임이다. 

source, extra, destination의 3개의 Peg가 있다. source에 각각 크기가 다른 n개의 디스크가 있어 이 3개의 peg중 어느 하나에나 삽입할 수 있다.

                                   source                                                                                  extra                                                                              destination

우리가 해야 할 일은 바로 source의 모든 peg를 destination으로 옮기는 것이다. 

제한 사항은 

첫째. 한 번에 하나의 디스크만 이동할 수 있다. 

둘째. 더 큰 디스크를 작은 디스크 위에 올릴 수 없다. 

 

해답을 말씀드리기 전에 먼저 아래는 연습할 수 있는 사이트에서 한번 시도해 보시기 바랍니다. 만만치 않을 것입니다. 

www.transum.org/Maths/Investigation/Tower_Of_Hanoi/Default.asp?Level=4

Tower Of Hanoi

그렇다면 이 문제 어떻게 풀 수 있을까요? 재귀를 사용해서 문제를 해결할 수 있습니다. 

 

1단계: destination을 사용하여 n-1 디스크를 source에서 extra로 이동

2단계: n번째 디스크(가장 큰 디스크)를 source에서 destination으로 이동

3단계: source를 사용하여 n-1 디스크를 extra에서 destination으로 이동

 

이제 이것을 힌트 삼아 직접 위의 사이트에서 문제를 해결해 보십시오. 

 

이제 이것을 JavaScript로 코드를 작성해 보겠습니다. 

/* num은 디스크의 숫자입니다. */
towerOfHanoi = function(source, destination, extra, num) {
	//base case
    if(num <= 0) {
    	return;
    }
    
    //recursive case
    towerOfHanoi(source, destination, extra, num - 1);
    
    console.log(`디스크 ${num} 을 ${source}에서 ${destination}으로 이동`);
    
    towerOfHanoi(extra, destination, source, num -1);
}
towerOfHanoi('source', 'destination', 'extra', 4)

이것을 콘솔 창에 찍어보면 다음과 같습니다. 

디스크 1 을 source에서 destination으로 이동
디스크 2 을 source에서 destination으로 이동
디스크 1 을 extra에서 destination으로 이동
디스크 3 을 source에서 destination으로 이동
디스크 1 을 extra에서 destination으로 이동
디스크 2 을 extra에서 destination으로 이동
디스크 1 을 source에서 destination으로 이동
디스크 4 을 source에서 destination으로 이동
디스크 1 을 extra에서 destination으로 이동
디스크 2 을 extra에서 destination으로 이동
디스크 1 을 source에서 destination으로 이동
디스크 3 을 extra에서 destination으로 이동
디스크 1 을 source에서 destination으로 이동
디스크 2 을 source에서 destination으로 이동
디스크 1 을 extra에서 destination으로 이동