하노이의 탑(Tower of Hanoi)

하노이의 탑(Tower of Hanoi)

• 첫번째 기둥을 A, 두번째 기둥을 B, 세번째 기둥을 C
• 작은 원반부터 큰 원반의 순서대로 1, 2, 3, ,,, 이라고 칭한다고 가정할 때.
• hanoi(N, A, B, C)는 hanoi()함수를 통해 N개의 원반을 A, B, C기둥을 통해 이동시킨다고 할때 사용되는 함수이다. 

// JavaScript
var hanoi = function(N, from, other, to) {
	
	if(N===1){

		div1.innerHTML += '원판[' + N + '] : ' + from + "---------&gt;" + to + "<br>";

	} else {

		hanoi(N-1, from, to, other);

	div1.innerHTML += '원판[' + N + '] : ' + from + "---------&gt;" + to + "<br>";

	hanoi(N-1, other, from, to);
	}
}

 

원반이 3개인 경우 (7번 이동)

 

원반이 4개인 경우 (15번 이동)

하노이의 탑은 재귀함수를 활용한 대표적인 문제이다.

재귀함수는 가장 나중에 호출된 함수가 먼저 실행되고 종료되어야 앞서 호출된 함수가 실행됨을 염두하자.
LIFO(Last In First Out)