F Sharp Programming/Solutions/Recursion

F# : Recursion and Recursive Functions Solutions

Faster Fib Function

The following function calculates the nth number in the Fibonacci sequence:

let rec fib = function
    | n when n=0I -> 0I
    | n when n=1I -> 1I
    | n -> fib(n - 1I) + fib(n - 2I)

The function above is neither tail-recursive nor particularly efficient with a computational complexity O(2ⁿ). The tail-recursive form of this function has a computational complexity of O(n). Re-write the function above so that its tail recursive.

You can verify the correctness of your function using the following:

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(10) = 55
fib(100) = 354224848179261915075

Solution

Examine the first 10 numbers in the Fibonacci sequence:

 n: fib(n)
---------
 0: 0
 1: 1
 2: 1
 3: 2
 4: 3
 5: 5
 6: 8
 7: 13
 8: 21
 9: 34
10: 55

Each number in the sequence is the sum of two numbers above it. If we hold the values of the previous two fib numbers in accumulating parameters, then we can calculate then next fib number very easily.

let fib n =
    let rec loop acc1 acc2 = function
        | n when n = 0I -> acc1
        | n when n = 1I -> acc2
        | n -> loop acc2 (acc1 + acc2) (n - 1I)
    loop 0I 1I n

The accumulator variables acc1 and acc2 correspond to fib(n - 1) and fib(n - 2) respectively.

We can test this function in fsi:

> let fib n =
    let rec loop acc1 acc2 = function
        | n when n = 0I -> acc1
        | n -> loop acc2 (acc1 + acc2) (n - 1I)
    loop 0I 1I n;;

val fib : Numerics.BigInteger -> Numerics.BigInteger

> [0I .. 10I] |> Seq.iter (fun x -> printfn "fib(%O) = %O" x (fib x));;
fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
fib(10) = 55
val it : unit = ()

> fib 100I;;
val it : Numerics.BigInteger = 354224848179261915075I

> fib 1000I;;
val it : Numerics.BigInteger 
= 434665576869374564356885276750406258025646605173717
80402481729089536555417949051890403879840079255169295
92259308032263477520968962323987332247116164299644090
6533187938298969649928516003704476137795166849228875I