masquerade0324のブログ

とある大学院生のメモ書き

Haskellでフィボナッチ数を返す関数fibを書く(Markdown記法を使ってみる)

フィボナッチ数列\{F_n\}の定義

フィボナッチ数列\{ F_n \}は以下のように再帰的に定義されます.

<br />
\begin{align}<br />
F_0 &= 0 \\<br />
F_1 &= 1 \\<br />
F_n &= F_{n-1} + F_{n-2} \ (n \ge 2)<br />
\end{align}<br />

Haskellによるフィボナッチ数を返す関数fibの実装

IntからIntへのフィボナッチ数を返す関数fibを書くと,次のようになります.

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

美しい!数学的な定義がそのまま現れていますね.よく知られているように,これを実際に書いて大きな数に対して適用すると,ものすごい遅いですし,スタックも使いまくるはずです.実際には次のように書くことが多いでしょう.

fastFib n = fibSub n 1 0

fibSub 0 a b = b
fibSub 1 a b = a
fibSub n a b = fibSub (n - 1) b (a + b)

こんな感じで書くと,それなりの速さの関数になると思います(上の定義は実行して確かめてないので間違ってたらごめんなさい).