フィボナッチ数を求めるプログラム

SICP読み始めた記念にHaskellで書いてみました。久しぶりなので非常に苦労しました。

再帰

main = print $ fib 50

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

反復

main = print $ fib 50

fib :: Integer -> Integer
fib n = fib_iter 1 0 n

fib_iter :: Integer -> Integer -> Integer -> Integer
fib_iter a b 0 = b
fib_iter a b n = fib_iter (a + b) a (n - 1)