What is memoization and where is it useful? Let us do a quick overview and dig into example code.

Memoization is a technique that can be used in long, recursive code to cache results from previous executions and speed up the overall process.

Consider a long repetitive operation where there is a good possibility that you will have the same arguments for the computation function more than once. What if we could make our program remember what had transpired in the last execution. We could then effectively shave-off cycles that had been done previously and speed up execution.

This is “memoization”.

We have seen in other posts that closures can remember parent’s state. Putting the two together, we can see a potential use of closures in memoization.

A practical example

Consider the totally practical problem of getting Fibonacci series up to a given number.

fibo(5) = [1, 1, 2, 3, 5]

Each number is equal to the sum of the previous two numbers, and the series starts from 0 or 1. We can generate the series using simple recursion.

1
2
3
4
5
6
7
8

let fibo = memoize(function(n) {
  if (n <= 1) return 1;
  else {
    return fibo(n - 1) + fibo(n - 2);
  }
});

fibo(5); // works!

The recursion counts down numbers while also adding results. So, you end up calling the function with same numbers more than once.

fibo(5) calls => fibo(4), fibo(3)
fibo(4) calls => fibo(3), fibo(2)
fibo(3) calls => fibo(2), fibo(1)
..

For an input 5, the following function calls happen -

1
2
3
4
5
6
7

fibo(5);
fibo(4);
fibo(3);
fibo(2);
fibo(2); // repeated
fibo(3); // repeated
fibo(2); // repeated

Memoization helps avoid evaluating the function evaluation for repeat calls. We will rewrite the above function to calculate Fibonacci series -

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

function fibo(n, cache) {
  cache = cache ? cache : {};

  if (cache[n]) {
    console.log("returning cached result for: ", n);
    return cache[n];
  }

  if (n < 2) {
    console.log("iterating..", 1);
    cache["0"] = 1;
    cache["1"] = 1;
    return 1;
  } else {
    console.log("iterating..", n);
    cache[n] = fibo(n - 1, cache) + fibo(n - 2, cache);
    console.log("cache: ", cache);
    return cache[n];
  }
}

fibo(5);

/* output
iterating.. 5
iterating.. 4
iterating.. 3
iterating.. 2
iterating.. 1
returning cached result for:  0
cache:  { '0': 1, '1': 1, '2': 2 }
returning cached result for:  1
cache:  { '0': 1, '1': 1, '2': 2, '3': 3 }
returning cached result for:  2
cache:  { '0': 1, '1': 1, '2': 2, '3': 3, '4': 5 }
returning cached result for:  3
cache:  { '0': 1, '1': 1, '2': 2, '3': 3, '4': 5, '5': 8 }
*/

We have done a really simple change - added an object called cache that persists across function calls. Each time there is an evaluation, the result is added to cache.

The recursion happens as normal for the first call.

For e.g. fibo(5) -

1. Evaluate expression fibo(4) + fibo(3)
2. Store results for 2, 1 in cache
3. Return results

For the next iteration - for fibo(4):

1. The expressions are fibo(3) + fibo(2)
2. 3 already exists in cache, and cache results are returned
3. Evaluation for fibo(2) happens normally

We can also see from the output that repeating instances will now not retrigger the full function, but return results from cache. (applicable for 1, 2, 3 as seen previously).

The new flow is -

1. Initiate program to calculate Fibonacci series for 5
2. Initiate cache
3. Add given input number (e.g. n-1) and its evaluation result to cache
4. Recursion with expression fibo(n-1) + fibo(n-2) to count down till number 1
5. If evaluation already exists, return cached result. As a result fibo(1), fibo(2) and fibo(3) are returned from cache when called the second time

When to use memoization?

When there is a long, oft-repeated evaluation cycle in your code. Make your code faster by utilizing cached results rather than full evaluation in a function.