하노이탑 호출 순서

하노이탑 코드

재귀 함수의 호출 순서를 정리했다.

void hanoi_t(int n, char from, char tmp, char to)
{
  if (n == 1)
    printf("...........원판 1을 %c에서 %c로 옮긴다.\n", from, to);
  else
  {
    hanoi_t(n - 1, from, to, tmp);
    printf("원판 %d를 %c에서 %c로 옮긴다.\n", n, from, to);
    hanoi_t(n - 1, tmp, from, to);
  }
}

main()
{
  hanoi_t(3, 'A', 'B', 'C');
}

n=3인 경우로 실행

편의상 그냥 A, B, C로 적었다.

hanoi_t(3, A, B, C)
hanoi_t(2, A, C, B)
hanoi_t(1, A, B, C)
원판 1을 A에서 C로 옮긴다.
원판 2를 A에서 B로 옮긴다.
hanoi_t(1, C, A, B)
원판 1을 C에서 B로 옮긴다.
원판 3을 A에서 C로 옮긴다.
hanoi_t(2, B, A, C)
hanoi_t(1, B, C, A)
원판 1을 B에서 A로 옮긴다.
원판 2를 B에서 C로 옮긴다.
hanoi_t(1, A, B, C)
원판 1을 A에서 C로 옮긴다.

이 설명이 가장 이해가 잘 되었다.