Memoization in short

What problem does memoization solve?
In a nutshell, it prevents ineffectiveness.

Why

The code is not as brilliant as you might think. Sometimes, it needs to repeat stuff over and over to do its job.

The great idea with memoization is to avoid unnecessary calculations. The program has already done the job, so let's save the results. Instead of computing the same things in memory repeatedly, you store them for later use.

It's the very concept of caching. If your script needs previous operations results in the next operations, it's the right candidate for memoization.

Pure functions and disclaimer

You need pure functions to apply memoization techniques. Those functions don't manipulate any state, and they have no side effects. They always return the same results for the same inputs, nothing more.

It's important to note that not all functions must be pure. There are some cases where memoization is even counterproductive.

Simple pattern

Here is a very simple example in JavaScript :

const myFunction = function(param) {
   if (!myFunction.memo[ param ]) {
       let outcome = {};// here is your operation instead
       myFunction.memo[ param ] = outcome;
   }
   return myFunction.memo[ param ];
};

myfunction.memo = {};

The code skips computation if the result is already available.

Recursion

Recursion is a little more complicated, but it can leverage the benefits of memoization techniques.

As you may already know, recursive functions call themselves. They usually have a condition that ends the recursion in a specific case. The recursive part happens in all other cases.

Here is an example in Python:

def fibo(n):
    if n <= 1:
        return n
    else:
        return fibo(n - 1) + fibo(n - 2)

The calculation is expensive. It happens because it executes several operations multiple times.

Why is that so?

fibo(2) executes fibo(1). fibo(3) executes fibo(2) and fibo(1), but fibo(2) executes fibo(1) too, etc.
In those conditions fibo(2000) is gonna take like forever...

Let's cache it :

fiboCache = {}

def fibo(n):
    if n in fiboCache:
        return fiboCache[ n ]
    if n < 2:
        value = 1
    else:
       value =  fibo(n - 1) + fibo(n - 2)
       fiboCache[ n ] = value
    return value

We use a dictionary to store values. This optimization is massive. Without it, the script would take a lot of time and memory to execute. It would probably kill memory unless you use tiny numbers as input, but in this case, using a function has very little interest.

You can test the boosted fibo with a crazy range:

for i in range(1, 2000):
     print(fibo(i))

Wrap

I hope you enjoy this short introduction to memoization. It's available in the vast majority of languages, so do not hesitate to use it appropriately.