재귀의 꽃 하노이 타워

---

하노이 타워 문제는 재귀(recursion)적으로 해결해야 하는 잘 알려진 문제입니다. 아래 JavaScript로 작성된 프로그램은 수강생들이 직접 만들어볼 수 있도록 수업을 하고 있습니다.
물론 처음에는 단순히 텍스트로 이 문제를 풀어봅니다. 그리고 GUI에 익숙해지면 아래 형태와 같이 구현해볼 수 있습니다.

재귀란 다시 돌아온다는 의미입니다. 즉, 어떤 함수가 자기자신을 다시 부르는 구조입니다.
수학에서는 흔한 구조입니다.
아래 수식은 팩토리얼의 수학적 정의입니다. 팩토리얼(!)의 정의에 다시 팩토리얼이 사용되고 있습니다. 이런 구조를 재귀구조(호출)라고 합니다.

$n!=\{\begin{array}{cc}1& \text{ if }n=0\\ n\times (n-1)!& \text{ if }n\ge 1\end{array}$

---

규칙

하노이 타워의 규칙은 단순합니다. 기둥 A에 있는 모든 디스크를 기둥 C로 옮기면 됩니다.
단, 한 번에 디스크 하나씩만 옮길 수 있으며, 큰 디스크를 작은 디스크 위로 옮길 수는 없습니다.
아래 미니 게임은 마우스로 디스크를 원하는 기둥으로 옮길 수 있으며, 몇 번만에 목표를 달성했는지 표시가 됩니다.

---

게임 직접 해보기

디스크는 마우스로 맨 위의 원반을 드래그 해서 원하는 기동으로 이동합니다.
자동 버튼은 어떻게 문제를 푸는지 보여주는 버튼입니다.
한 단계 이동은 단계별로 디스크의 이동을 볼 때 사용하는 버튼이며,
원판 개수는 최소 3개 그리고 최대 10개 입니다.
자동 이동 속도는 자동 옵션에서 이동 속도를 제어하는 버튼 입니다.

---

🧩 하노이 타워: '64개의 황금 원판' 전설

• 인도 베나레스(Benares)의 브라만 사원에는 64개의 황금 원판이 세 개의 기둥 위에 쌓여 있다.
• 사제들은 신이 정한 규칙(하노이 타워 규칙)에 따라 원판을 하나씩 옮기고 있다.
• 64개의 원판을 모두 옮기는 순간, 세상은 종말을 맞는다.

이 전설은 실제 고대 신화가 아니라, 퍼즐이 소개된 1884년 프랑스 잡지 La Nature에 실린 이야기이며, 퍼즐을 더 신비롭고 고대의 지혜처럼 보이게 하려는 마케팅용 설정이었습니다.

---

✔️ 하필이면 왜 64개?

64개의 원판을 옮기려면 최소

2⁶⁴ - 1

번의 이동이 필요하고, 초당 1번씩 옮긴다면 약 5850억 년이 필요합니다.
이는 우주의 나이보다 훨씬 길다고 광고에서 강조 했습니다.
사실 이정도 시간이면 세상이 남아 있는 것이 더 이상하긴 하죠.

---