Recursive Fibonacci with F#

02 Jul 2009

Fibonacci number is the typical example of recursive usage. However, as pointed in Code Complete, when programmed as purely recursive, it is very painful.

Remark: this post is very straightforward, but what I'm really doing here is playing around with F# to learn.

In case you don't know Fibonacci number, please see this article, but it can be summarized as:

F(n) = F(n-1) + F(n-2)
F(1) = 1
F(2) = 1

Here is the F# sample of a recursive Fibonacci function:

let rec fib n =
    match n with
    | 1 | 2 -> 1
    | n -> fib(n-1) + fib(n-2)

Plain simple. However, you can easily spot that we are calculating things over and over again.

To see how painful it gets when the number get large, let's benchmark this using the Stopwatch:

let n = 40
let sw = Stopwatch()

sw.Start()
let x = fib(n)
sw.Stop()

Console.WriteLine("fibRec({0}): {1}", n, x)
Console.WriteLine("Time: {0}", sw.ElapsedMilliseconds)

On my current laptop, using n as 40, it takes 2858ms. For n = 41, it takes 4698ms. For n = 42, it takes 7504ms (the time it takes for n = 40 plus n = 41, as we are calculating over and over), etc. If I launch it with n = 50, It should take about six minutes. For n = 60, it will take 12 hours.for n = 70, it'll take more than 62 days...

Not very effective indeed.

So, the best way for this to be faster is to find a way to not calculate thing again and again. You can do this using a while or for statement, but I want to do this recursively. It has previously been done by Bart De Smet in C# using memoization (which is much better than what I came up with...), but I'll do this with an array.

Here's the plan:

Use an array to store previously calculated values;
Each value in the array will be initialized as 0;
When trying to fetch a value in the array, if it is 0, let's calculate the value by calling the function again.

Here is the way I did this in F#:

let fib n =
    let lookup = Array.create (n+1) 0
    let rec f = fun x ->
        match x with
        | 1 | 2 -> 1
        | x ->
            match lookup.[x] with
            | 0 ->
                lookup.[x] <- f(x-1) + f(x-2)
                lookup.[x]
            | x -> x
    f(n)

Remarks:

The "wrapper" function fib is not recursive, as we don't call it over and over again;
The array's size is n+1, so we can call on it using x and not having to do x-1 all the time. One value is wasted, but off-by-one errors are avoided;
The lambda function f is recursive as we have to call it over and over again.
The array is captured and used in the lambda function f (closure).

Now let's run the benchmark once more and see the result.

For n = 42, the time is... 1ms. For n = 80 (that would take 21 years recursively, although it would probably overflow), the time is 1ms also. A bit more difficult to read, but not too bad regarding performances.

What Did I Learn?

For the record, here's what I learned from doing this:

rec keyword simply means that the function is able to call itself. If omitted, the function is not visible inside it's own body;
match statements can have logical expressions on one line to mach multiple values (in the example above, 1 and 2 have to return 1);
to get an element of an array, you use the array.[x] and not the usual array[x].

There is probably a good explanation for each of these points, but I don't have it yet. I'm sure It'll make sense once I get to know the language a bit better.

F# 1