하노이탑 이해하기

void hanoi(int n, char from, char tmp, char to) {
  if(n==1)

    printf("move disk #1 from %c to %c.\n", from, to); // [1]
  else{ // ****
    hanoi(n-1,from,to,tmp); [ㄱ]
    printf("move disk #%d from %c to %c to.\n",n,from,to); // [2]
    hanoi(n-1,tmp,from,to); [ㄴ]

  }
}

hanoi(3, 'A','B','C'); 을 호출합니다.

hanoi(3, from, tmp, to) 가 시작됩니다. n은 3, from 은 'A', tmp는 'B', to는 'C' 입니다.

......n 이 3입니다. else // **** 이하를 실행합니다.

...... hanoi'(2, 'A', 'C', 'B'); 를 호출합니다.[ㄱ]

...... hanoi'(2, from, tmp, to) 시작, n' 은 2 , from'은 'A', tmp' 는 'C', to' 는 'B' 입니다.

............. n이 2입니다. // ***** 이하

..............hanoi"(1,'A', 'B', 'C'); 호출 [ㄱ]

..............hanoi"(1, from, tmp, to) 시작, n" 은 1, from" 는 ' A', tmp" 는 'B', to" 는 'C' 입니다.

....................n이 1입니다. [1]을 실행합니다. 1을 A에서 C로 옮긴다고 출력합니다. 끝이납니다.

..............[ㄱ] 이 끝났습니다. 그다음 줄인 [2]를 실행합니다.

..............[2] 2를 A 에서 B로 옮긴다고 출력합니다.

..............hanoi"(1,'C', 'A', 'B'); 호출 [ㄴ]

..............hanoi"(1, from, tmp, to) 시작, n" 은 1, from" 는 ' C', tmp" 는 'A', to" 는 'B' 입니다.

....................n이 1입니다. [1]을 실행합니다. 1을 C에서 B로 옮긴다고 출력합니다. 끝이납니다.

..............[ㄴ] 이 끝났습니다. hanoi'(2,...)[ㄱ]이 끝났습니다. [2]를 실행합니다

...... [2] 3을 A에서 C로 옮긴다고 출력합니다.

...... hanoi'(2, 'B', 'A', 'C'); 호출 [ㄴ]

...... hanoi'(2, from, tmp, to) 시작, n' 은 2 , from'은 'B', tmp' 는 'A', to' 는 'C' 입니다.

............. n이 2입니다. // ***** 이하

..............hanoi"(1,'B', 'C', 'A'); 호출 [ㄱ]

..............hanoi"(1, from, tmp, to) 시작, n" 은 1, from" 는 'B', tmp" 는 'C', to" 는 'A' 입니다.

....................n이 1입니다. [1]을 실행합니다. 1을 B에서 A로 옮긴다고 출력합니다. 끝이납니다.

..............[ㄱ] 이 끝났습니다. 그다음 줄인 [2]를 실행합니다.

..............[2] 2를 B 에서 C로 옮긴다고 출력합니다.

..............hanoi"(1,'A', 'B', 'C'); 호출 [ㄴ]

..............hanoi"(1, from, tmp, to) 시작, n" 은 1, from" 는 'A', tmp" 는 'B', to" 는 'C' 입니다.

....................n이 1입니다. [1]을 실행합니다. 1을 A에서 C로 옮긴다고 출력합니다. 끝이납니다.

..............[ㄴ] 이 끝났습니다. hanoi'(2,...)[ㄴ]이 끝났습니다.

모두 끝났습니다.