現在Recursionに取り組んでいる。 そこで学んだことをメモする。
ハノイの塔
3本の棒と複数の円盤を用いたシンプルなパズル。 円盤を目的の棒に、なるべく少ない移動回数で移動させるというもの。 円盤は全てサイズが異なり、サイズの小さい円盤は大きい円盤の下には積めない。 数学的に色々な解法があり、よく題材になる定番の問題（らしい）。
実装
以前の記事でも書いた通り、漸化式が書ければ実装できる。
少しこの漸化式に手こずったが、考え方が掴めるとすんなり実装できた。
漸化式の考え方としては以下の通り。
円盤がn枚存在するとする。この移動回数をF(n)とする。
その際「最下部の最も大きい円盤」と「残りのn-1枚」の2つの構成と見なす。
まず「残りのn-1枚」を何かしらの方法で「最下部の最も大きい円盤」以外の棒の上に移動させ、（= F(n-1)）
「最下部の最も大きい円盤」を目的の棒に移動し、（= F(1) = 1）
最後に「残りのn-1枚」を何かしらの方法で「最下部の最も大きい円盤」に再度移動させる。（= F(n-1)）
なのでn枚の円盤を動かす回数は以下の漸化式で書ける。
F(1) = 1 F(2) = 3 # これは円盤が少ないので試せばすぐに分かる F(n) = 2 * F(n-1) + F(0)
以上より、pythonで実装すると次のようになる。
def towerOfHanoi(n): if n == 1: return 1 if n == 2: return 3 return towerOfHanoi(1) + 2 * towerOfHanoi(n - 1)
