コンピュータの再帰プログラムを語る「ハノイの塔」


円板の枚数が何枚増えても最小の移動回数で移動が達成できる板の動
かし方（アルゴリズムとしておこう）があります。

　図の場所 A に、下から大小の順に３枚の板を積み上げる。下記ルールで、 場
所 C に Aと同じ形に移しかえるには何回板を動かせばよいだろうか。


ルール１　；　板を１つの箇所から別の箇所に移しかえるのは１回１枚だけ。
ルール２　；　どの板も、それより小さい板の上に重ねて移してはならない。

　実際動かすと、２枚の場合は３手で移動終了。３枚の場合は７手で移動終了する。
　ところで、この３枚の実際に動かす過程をもう一度よく見ると、次のような特徴
的なことに気付く。

３枚の場合の動画、4枚の場合の動画

つまり、移動途中3手目で Ｂ もしくは Ｃ に２枚動かした結果の場合が一度起こり、
その後は、3枚目の板を移動（1手）し、つぎにその上に2枚を移動（３手）すれば3
枚の移動が完了する。このことから、3枚の板の移動手順は、３＋１＋３＝７手とい
う手順計算できる。同じく、4枚の場合も注意深く動かすと、３枚動かした結果（7
手）の場合が一度起こり、その後は4枚目の板を移動（1手）し、つぎにその上に3枚
の移動（7手）を再現すれば4枚の移動が完了するので、その移動手順の総数は、
　　７＋１＋７=１５
と求められる。
　以下同様ですが、この、
　　もし、与えられた問題よりも規模の小さい問題が解ければ、その解を用いて、
　　より規模の大きな問題も解けるに違いない
というのが「再帰(さいき)　の考え」といいます。
　この「再帰の考え」を用いて一般項anの式をノートに求めてみよ。

　解答は、左の枠内にある＜再帰から漸化式へ＞をクリックすればあります。