✲゚。.ヾ(⌒(ノ'ω')ノ☆.。

変色系男子の日常。

いろんなフィボナッチ (再帰)

フィボナッチ数 を求めるプログラムを 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 にブロックを渡す方法は目からウロコだった。Σ(゚Д゚