For those of us who study computer science and algorithms, the study of recursion has an iconic example: The Fibonacci sequence.

I truly believe that this is clearly the worst scenario for using recursion. Some of you may think that it’s a great example due to the simplicity of the code. It is short, easy to remember, easy to read, even beautiful.

For example, I found this Swift implementation quite short, and I don’t believe it is possible to write one in fewer lines.

func fib(n: Int) -> Int {
    guard n > 1 else { return n }
    return fib(n-1) + fib(n-2)
}

It is clear the use of recursion, the function only has two lines and F(0) and F(0) are solved in O(1). While the rest of the numbers is resolved in O(2^n). (For more information about Big-O notation take a look at this Wikipedia post).

Now, let’s do some maths. We will see that it takes to calculate F(n) when N is less than 6

F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 0 + 1 = 1
F(3) = F(2) + F(1) = (F(1) + F(0)) + F(1) = 2
F(4) = F(3) + F(2) = (F(2) + F(1)) + (F(1) + F(0)) = 3
F(5) = F(4) + F(3) = (F(3) + F(2)) + (F(2) + F(1)) = 5
F(6) = F(5) + F(4) = (F(4) + F(3)) + (F(3) + F(2)) = 8

---

The first approach to optimise this function is to realise that some numbers are calculated several times. So… we can implement a cache! We can have a cache of F(n) and if it’s in the cache avoid the recursion. We are still on an approach that is not optimal neither in time nor in complexity.

This new approach can introduce a new problem when N is big. The algorithm now runs faster, but it takes too much memory!

---

But if we look a little bit further, every number in the sequence needs the two previous ones, and no more than that. So, what about having a small cache of the last two calculated number.

So we can have a non recursive approach of the Fibonacci sequence, solved in O(n) by saving the last two calculated numbers, and “switching them” as I show in the following Swift code.

func fib (n: Int) -> Int {
    if n < 2 { return n }
    var result = 0, fa = 0, fb = 1
    for  _ in 2...n {
        result = fa + fb
        fa = fb
        fb = result
    }
    return result
}
for i in 0...6 {
    debugPrint("f(\(i)) = \(fib(n: i))")
}

Testing it will produce the same result as doing the maths. But this time this algorithm is O(n) and it is very very optimal in terms of memory.

for i in 0...6 {
    debugPrint("f(\(i)) = \(fib(n: i))")
}

"f(0) = 0"
"f(1) = 1"
"f(2) = 1"
"f(3) = 2"
"f(4) = 3"
"f(5) = 5"
"f(6) = 8"