Fibonacci Series and Memoization with Swift Examples

Fibonacci series

Fibonacci numbers (spelling – Fibonacci^[2]) — elements of the numerical sequence
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, … (sequence A000045 V OEIS),
in which the first two numbers are 0 and 1, and each subsequent number is equal to the sum of the two previous numbers^[3]. Named after the medieval mathematician Leonardo of Pisa (known as fibonacci)^[4].
– Wikipedia

The Fibonacci series is often mentioned in job interviews because it demonstrates many powerful techniques, including recursion. He is a great example of what we call memoization. Understanding the Fibonacci series and how it works is very helpful.
Mathematically, the Fibonacci series is a sequence of numbers that follow this equation: F(n) = F(n-1) + F(n-2). This sequence occurs in various interesting contexts, such as in nature, in shells, spiral structures and galaxies, and in the design of Roman floors, and even brokers use the Fibonacci series to predict stocks.

func fib(_ n: Int) -> Int {
    if n == 0 {
        return 0
    } else if n == 1 {
        return 1
    } else {
        return fib(n - 1) + fib(n - 2)
    }
}

In the code, the Fibonacci series looks like this: for F(0) and F(1) we return their values directly, and then the algorithm is reduced to this line – return fib(n-1) + fib(n-2). This is the key point of the algorithm and demonstrates the use of recursion.
However, the Fibonacci series has a problem: as the numbers in the sequence increase, the algorithm takes more and more time to calculate. This is due to the fact that the time required for calculations grows exponentially, and the complexity of the algorithm is O(2^n). This makes the calculations very costly.
Our task is to find a way to optimize this algorithm and make it faster. This is where a powerful technique known as memoization comes in, which is important to know and understand.

memoization

To understand memoization, we need to consider the problem with the Fibonacci series. For prime numbers, such as numbers up to F(5), the Fibonacci series is fairly fast. However, when calculating numbers of a higher order, recalculating the numbers becomes very time consuming.

Memoization is an optimization technique that speeds up algorithms by caching or storing the results of computations for use in future computations. In the case of the Fibonacci series, we can create a dictionary (let’s call it “Memo”) to store the previously computed numbers. Then, when we calculate each number of the Fibonacci series, we store the result in an array and return it. This way, next time we don’t have to calculate this number again and again.

var memo = [Int: Int]()

func fib(_ n: Int) -> Int {
    if n == 0 { return 0 }
    else if n == 1 { return 1 }
  
    if let result = memo[n] { return result }
  
    memo[n] = fib(n - 1) + fib(n - 2)
    return memo [n]!
}

Thanks to memoization, the efficiency of the algorithm increases significantly. Now, instead of calculating the Fibonacci series of 30 numbers in 19 seconds, we can calculate thousands of numbers. This is an increase of 3333%. We have changed the algorithm from exponential (O(2^n)) to linear (O(n)).

This is why the Fibonacci series and memoization are great interview examples. They combine recursion and memoization, showing how to make a costly algorithm faster. Knowing and understanding the Fibonacci series and memoization will help you solve problems like this quickly and efficiently.

import UIKit

func fibNaive(_ n: Int) -> Int {
    print(n)
    if n == 0 {
        return 0
    } else if n == 1 {
        return 1
    } else {
        return fibNaive(n - 1) + fibNaive(n - 2)
    }
}

fibNaive(20) // 20 = 13s / 22 = 54 s
var memo = [Int: Int]()

func fib(_ n: Int) -> Int {
    if n == 0 { return 0}
    else if n == 1 { return 1 }

    if let result = memo[n] { return result }

    memo[n] = fib(n - 1) + fib(n - 2)

    return memo[n]!
}

fib(22) // 90 max

As for creating one of them from scratch, it’s very simple. I present to your attention two implementations: one naive, which does not remember or store anything, and the second, where we use memoization and store our results as they are calculated.

Let’s dwell on the memoized version for a moment to show how long it takes to perform a very small Fibonacci calculation on the number 20. If we run it on a prime number like 20, you will see that the counter works by counting the same numbers over and over again and again. On average, it takes about 13 seconds, which is not that much. Now if I increase it by one or two it will take even longer. This is exponential growth, increasing in size, and very small increments of the number take more and more time. That’s how the Fibonacci series works, and that’s why it’s so expensive.

Now let’s compare this to the memoized version and see what it’s like to store these values. In the second case, we will store our results in a dictionary. Every time we calculate F(n-1) + F(n-2), we will store it in the key represented by N, whatever the number is at that moment (20, 21, 22, etc.) . We will just save this result. Then, as successive calculations are performed, if we can extract the result from the dictionary, we will simply return it without calculating it again.

Conclusion:

This is useful not only for Fibonacci series, but for everything that involves expensive calculations that can be saved, cached and used in future results.
This is the power of memoization.
It is used for a variety of things.
The Fibonacci series is a great example. When it comes to a real interview.
I have heard people being asked to reproduce the Fibonacci series.
This is not a huge algorithm, it boils down to one line and two cases: the end is zero and one. But my advice is just remember this line, because it demonstrates such a thing as recursion.
Once you understand this, it’s very easy to move on to a memoized example where you can demonstrate how to take a labor-intensive algorithm and make it more efficient. You know – it’s called memoization.