Memoization is an optimization technique used to improve performances of a given algorithm/program by storing the result of expensive function calls and returning a cached result whenever the same input occurs again.

We’ll be using the Fibonacci Sequence as an example to see Memoization in depth.
We actually have multiple ways to compute the Fibonacci Sequence in JavaScript; two of the most popular ways are the Iterative and the Recursive ones:

Iterative

function fibonacci(num) {
  let seq = [1, 1];

  for (let i = 2; i < num; i++) {
    seq[i] = seq[i - 1] + seq[i - 2];
  }

  return seq[num - 1];
}

Recursive

const fibonacci = (num) => num <= 1 ? 1 : fibonacci(num - 1) + fibonacci(num - 2);

The recursive one is actually more coincise and clearer but comes with a cost: performances.
As we’ve seen in the previous article, Adopting Memory Safe Recursion, we can use trampolines to convert recursive calls in a while loop, which can help us improving both performances and memory safety.
But if we just have a performances problem, we can act differently adopting Memoization:

const cache = {};

function fibonacci(num) {

  if(num < 1) return 0;

  if(num < 2) return 1;

  if (num in cache) return cache[num];

  const value = fibonacci(num - 1) + fibonacci(num - 2);

  cache[num] = value;

  return value;
}

What’s happening here?
We’re defining an empty object called cache which, as you may guess, will be our cache for the Fibonacci algorithm.
Then, we check if the number passed in as an argument is already set in our cache. If that is the case, we return the cached value with no more computations.
If the number is not set in our cache, we compute it, store it in our cache and then return it.

Wanna see some numbers?
I’ve made a little benchmark for the the Iterative, Recursive, Memoized solution and guess what? The Memoized solution is absolutely the fastest one!

Computing the 10th Fibonacci number:

Recursive: 1877 ms
Iterative: 647 ms
Memoized: 511 ms

Memoization in JavaScript

We can also define a generic and reusable memoize function:

function memoizer(fn) {

  let cache = {};

  return function(arg) {
    if(cache[arg]) {
      return cache[arg];
    } else {
      let result = fn(arg);
      cache[arg] = result;
      return result;
    }
  }

}

That way, we can wrap any function inside our memoizer, which will create a cache for the function execution:

memoizer(fibonacci)(10);

But how does it work?
As you can see, the memoizer function declares a new cache variable and then returns a function which takes an argument.
If that argument already exist in our cache, then we return its cached value, with no more computation needed.
If that argument is not cached, we just compute the function against it and then we store the result in our cache.
It’s incredible how such an easy function can be so powerful!

Did you like this article? Consider becoming a Patron!

This article is CC0 1.0 (Public Domain) licensed.