サブルーチンを再帰的に呼び出す例としてプログラミングのテキストによく「ハノイの塔」が登場する。
元の話として聞いている話の真偽は定かではないが次のようなもの。
ハノイのとある寺に直径の異なる円板が64枚ある。大きな円板を小さな円板の上に置くことはできない。円板を置くことのできる場所は3箇所。そのうちの1箇所から別の1箇所に移している。1度に移せるのは1枚。全部を移し終えた時が世界の終わり。
これは数列の漸化式のネタとしても使える。
簡単な2枚の場合を例示する。AからCに移すものとする。1が2より小さいものとして表示。
A12BC Aから1をBに移す。
A2B1C Aから2をCに移す。
AB1C2 Bから1をCに移して終わり。
ABC12
では、4枚の場合はどうでしょう?考えてみてください。答えは明日。