いろんなフィボナッチ (再帰)
フィボナッチ数 を求めるプログラムを Ruby で書くと一般的にはだいたいこんな感じだと思う。
def f1(n) (0..1).include?(n) ? n : f1(n - 2) + f1(n - 1) end f1(10) #=> 55
しかし今回は、最近知った Ruby の裏ワザ的なことを復習する意味も込めて、
ちょっと変わった書き方を紹介してみる。
まずは、デフォルト引数を使った書き方。
def f2(n, m = (0..1).include?(n) ? n : f2(n - 2) + f2(n - 1)) m end f2(10) #=> 55
どういう用途があるのかはよく分かんないけど、デフォルト引数を使って再帰のプログラムが書けるw
次に Hash.new を使った書き方。
def f3(n) Hash.new {|hash, i| hash[i] = (0..1).include?(i) ? i : hash[i - 2] + hash[i - 1]}[n] end f3(10) #=> 55
これは、
- Hash#new に2引数のブロックを渡した場合、存在しない key にアクセスしようとした際にそのブロックが実行される。
- 第1引数には Hash 自身が渡されるため、計算結果を Hash に保存しておくことが出来る (メモ化) 。
という性質を利用している。
メモ化を行なって一度計算した結果を覚えているので、
例えば f3(1000) すなわち n = 1000 でも一瞬で処理が終わる!素晴らしい!
※ さすがに f3(5000) とかは stack level too deep で無理。
※ 前に紹介したメモ化を使用しない方法だと、計算回数が膨大になり f1(40) くらいでも相当時間が掛かる…
Hash.new にブロックを渡す方法は目からウロコだった。Σ(゚Д゚