Fibonacci in F# - Five Ways

Recrusion is cool! And Fibonacci is a standard algorithm to examine when exploring recursion.

Here are five ways to generate a fibonacci sequence in F#. Some good, some bad.

Recursion in F#

Before diving into Fibonacci, a brief primer on functions and recursion in F#.

Here is a simple function that performs addition.

let add (x, y) = x + y

F# deduces the types for you, but you could have also specified the types as well.

let add (x: int, y: int): int = x + y

Recursion is when a function call itself, and in F# the rec keyword is required.

let rec brokenFunc (x) = brokenFunc(x + 1)

Simple enough. On to Fibonacci.

The Broken Way

If you google Fibonacci, learn that it’s just the addition of the previous 2 terms. You might code something like this.

//throws StackOverflowException
let rec fib1(n: int): int = fib1(n - 1) + fib1(n - 2)

let run = fib1(5) |> printfn"%i"

Except there’s no base case, so this algorithm will continue indefinitely. Or until your stack runs out of space. 🤣

Working, but not Great

Okay, it needs to end at some point. So lets add a base case.

let rec fib2(n: int):int = 
    match n with
    | 0 | 1 -> n
    | n -> fib2 (n-1) + fib2 (n - 2)
    
let run = fib2(10) |> printfn"%i"

We’re using a match statement to return whenever our case is 0 or 1. This works for very small numbers. But in bigger numbers, we again run into problems.

Since ever call to fib2, makes two calls to itself, expotential growth.

Iterative Approach

We could get rid of recursion, and just use a loop and two mutable values.

let fib3 n = 
    match n with 
    | 0 -> 0
    | n -> 
        let mutable last = 0
        let mutable next = 1
        for i in 1 .. (n - 1) do
            let temp = last + next
            last <- next
            next <- temp
        next

let run =
    fib3 2 |> printfn "%i" |> ignore
    fib3 3 |> printfn "%i" |> ignore
    fib3 40 |> printfn "%i" |> ignore

It’s efficient and doesn’t have the expotential growth problem. But for loops and and mutable values aren’t the most functional way to approach this problem.

Memoization Approach

What is memoization?

Memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

wikipedia

It stores function results we’ve already computed, and will return the previous results instead of having to recompute. And since we’re using F#, we’ll use composition.

Here’s our memoize function.

let memoize f =
    let dict = Dictionary<_, _>();
    fun c ->
        let exist, value = dict.TryGetValue c
        match exist with
        | true -> value
        | _ -> 
            let value = f c
            dict.Add(c, value)
            value

Parameter f is a function itself. dict is our dictionary. Anytime our provided function f is called, we first see if the result of that function exists in dict.

If it does, we return that value. If not, we compute the value, add it to the dict, then return the value. Then next time we’ll have that value ready to return instead of recomputing.

Lets take our “Working, but not Great” fibonacci, now called fib4:

let rec fib4(n: int):int = 
    match n with
    | 1 | 2 -> n
    | n -> fib4 (n-1) + fib4 (n - 2)

And we pass that function to memoize:

//composing fib4 with our memoize function
let memoFib = memoize fib4

let run =
    memoFib 2 |> printfn "%i" |> ignore
    memoFib 3 |> printfn "%i" |> ignore
    memoFib 40 |> printfn "%i" |> ignore

We now avoid a lot of expensive recomputations because we’re memoizing our function call.

The Seq Approach

Up till now, our fibonacci functions have returned a single value. If you called fib (10), you’d get the 10th value.

We can leverage sequences to compute the entire fibonacci sequence instead of a single value.

let fib5 n = 
    let mutable last = 0
    let mutable next = 1
    seq {
        0
        1
        for i in 1 .. (n - 1) do
            let temp = last + next
            last <- next
            next <- temp
            next
        }

let run = fib5 10 |> Seq.iter (printfn "%d")

Output:

As you can tell, there’s no stopping point in this sequence. It will keep computing values as long as you keep calling it.

Have Fun with F#

That is 5 different ways of implementing fibonacci in F#.

Until next time.