Haskell入門 フィボナッチ数列を末尾再帰で速くする
参考ページ
お気楽 Haskell プログラミング入門
-- fibo.hs -- 普通 fibo :: Integer -> Integer fibo n = if n == 0 || n == 1 then n else fibo (n - 1) + fibo (n - 2) -- 末尾再帰 fibo_tail :: Integer -> Integer fibo_tail n = fibo_sub n 0 1 where fibo_sub 0 a _ = a fibo_sub n a b = fibo_sub (n - 1) b (a + b)
実行
Prelude> :set +s Prelude> :l fibo.hs *Main> fibo 30 832040 (3.20 secs, 769,826,264 bytes) *Main> fibo_tail 30 832040 (0.01 secs, 72,976 bytes)