Towers of Hanoi

[하노이의 탑]

Recursion하면 약방의 감초처럼 등장하는 개념 삼대장 중의 하나 되시겠다. 나머지는 팩토리얼이랑 피보나치 수열..

대략적인 코드는 이렇다.

private  static void solveTower(int num, int fromPeg, int toPeg,
			int tempPeg) {
 		if (num > 0) {
 			// move a disc from the fromPeg to the tempPeg
			solveTower(num - 1, fromPeg, tempPeg, toPeg);

 			System.out.println("Disc moved from " + fromPeg + " to " + toPeg);

 			// move disc from the tempPeg to the toPeg
			solveTower(num - 1, tempPeg, toPeg, fromPeg);
		}
	}

처음에 이 코드를 비롯한 다른 Recursion을 이용한 함수들도 어떤 원리로 작동되는지 이해하느라 진땀을 뺀 기억이 난다.

엥? 함수 안의 또다른 함수에 진입하면 도대체 어떤 순서로 일들이 일어나는거지?? 이러면서..

지금도 이걸 참 말로 풀이하려고 하면 제대로 설명을 못하겠다.

그런 의미에서 소스코드가 돌아가는 과정을 한 번 순서대로 따라가면서 풀이해보자.

참조

http://www.ibm.com/developerworks/websphere/techjournal/1307_col_paskin/1307_col_paskin.html

http://hanoitower.mkolar.org/algo.html