What is memoization?

We all know how useful a recursive algorithm can be, when it comes to perform actions which are repetitive in nature, some may argue that we can use loops instead of recursion, but that’s something which I will cover in a different post.

Let’s see how can we use recursion to calculate fibonacci numbers.

Numbers in fibonacci series looks like below.

1
2

// First 13 numbers in fibonacci series
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ....

If we notice, every number in the series after first 2 numbers is a sum previous 2 numbers in the series, which can be written as X_n = X_n-1 + X_n-2

1
2
3
4
5
6
7

function fibonacci(n){
    if(n === 1 || n === 2){
        return 1;
    }

    return fibonacci(n-1)+fibonacci(n-2);
}

Let’s generate 6^th fibonacci number using above program.

To compute 6^th fibonacci number, our function needs 5^th and 4^th fibonacci numbers, but we don’t have those numbers, so our function first needs to calculate them, same goes for 5^th and 4^thnumbers, this process will continue until we get the 1^st fibonacci number.

Time required to compute fibonacci numbers with above program is exponential.

We can optimized this function by using a technique called Memoization.

Memoization

Memoization is a technique used for improving the performance of recursive algorithms, It involves rewriting the recursive algorithm in such a way so that as answers to problems are found, they are cached, Future recursive calls can look up results in the cache rather than having to recalculate them.
Memoization improves performance because partial results are never calculated twice.

Let’s re-write the function used to generate the fibonacci sequence by applying memoization technique.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

var f_cache = {};
function fibonacci(n){
    var fromCache = f_cache[n];
    if(fromCache)
        return fromCache;

    if(n === 1 || n === 2){
        return 1;
    }
    
    var num = fibonacci(n-2)+fibonacci(n-1);
    f_cache[n] = num;

    return num;
}

With optimized function let’s generate 6^th fibonacci number.

To compute 6^th fibonacci number, our function still needs 5^th and 4^th fibonacci numbers, but it doesn’t need to recalculate them on future calls, because it can get the pre computed numbers from the cache.

Time required to compute fibonacci numbers with optimized program is linear O(n) because partial results are never calculated twice.