Calculate the Fibonacci number $F_n$ in Haskell. Some solutions from the Haskell Wiki.
This get's slow pretty quickly. The runtime complexity is $\cal O(fib(n))$.
fibG n
| n == 0 = 0
| n == 1 = 1
| otherwise = fibG (n-1) + fibG (n-2)
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
It works only for very small values of n
.
fib 10
fibG 10
55
55
True
The state of the calculation is passed in a tuple. Uses pattern matching with guards. The accumulator helps to make this $\cal O(n)$.
fib n = go n (0,1)
where
go 0 (a, _) = a
go n (a, b) = go (n-1) (b, a+b)
fib 50
12586269025
Calculates the infinite sequence of Fibonacci numbers. Then picks the nth element. Relies on lazy evaluation to prevent endless recursion. Also $\cal O(n)$. Can be considered the most idiomatic Haskell version.
fib n = fibs !! n
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fib 50
12586269025