Aventures in F# - Fibs

Today's post is about the famous Fibbonaci sequence: 0, 1, 1, 2, 3, 5, 8, ...

I will present a recursive and an iterative F# approach to generating the sequence.

The Fibbonaci number n = Fib(n) is generated as follows:

Fib(n) = Fib(n-2) + Fib(n-1) where Fib(0) = 0 and Fib(1) = 1

The condition Fib(0) and Fib(1) are the anchor to end the recursion and otherwise it is dug into the recursion. Consequently, ...

1. Recursive Approach

let rec FibRec n =
if n = 0 then 0
else if n = 1 then 1
else (FibRec (n-2) + FibRec(n-1))
;;

As you can see the function is rather straightforward and follows the definition closely. However, its recursive nature make it rather unsuiting for large values of n - you will notice that for large values of n the recursion slows the process down.

2. Iterative approach

let FibIt n =
if n = 0 then 0
else if n = 1 then 1
else
let fibA = Array.create (n+1) 0
fibA.[0] <- 0 fibA.[1] <- 1 for i = 2 to n do
fibA.[i] <- fibA.[i-2] + fibA.[i-1] fibA.[n] ;;

As you can see the iterative approach employs Fib(0) and Fib(1) equally as anchors. However, it uses a for loop starting at two to fill an array at index i with the Fibbonaci number Fib(i). Clearly, we do not need the array but it will come in handy at a later stage.

Although being faster, i.e. compare the recursive approach with the iterative approach for Fib(40) and you will notice some time difference, both approaches suffer data overflow. This means that Fib(48) displays correctly but Fib(49) wraps around the integer boarder and becomes a negative number. Therefore we have to find a way around this problem - probably the next time.

I have come around some valuable resources with respect to F#

Marius Bancila's Blog: http://mariusbancila.ro/blog/
Robert Pickering's Strange Blog: http://strangelights.com/blog/