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] for i = 2 to n do fibA.[i] As you can see the iterative approach employs Fib(0) and Fib...