Memoization: Understanding the concept

I’ll go straight to the point here. Memoization is the programmatic practice of making long recursive/iterative functions run much faster.

But how? Well, the speed is achieved by caching function results after its execution so they can be immediately returned the next time the function is called with the same arguments.

Here’s a basic example.

const add = (a, b) => a + b
console.log(add(2,3)) // => returns 5

Every time we call this function, a calculation is going to be performed and a value returned.

Now lets create a simple memoize function that takes another function and modifies it to memoize calls.

const memoize = (fn) => {
  let cache = {};
  return (...args) => {
    let n = JSON.stringify(args);
    if (n in cache) {
      console.log('Fetching from cache', n);
      return cache[n];
    }
    else {
      console.log('Calculating result', n);
      let result = fn(...args);
      cache[n] = result;
      return result;
    }
  }
}

Now we can easily memoize any pure function, like our add function. Since memoize is a high order function, we have two ways of doing this. One is creating a new memoized function, like below.

const add = (a, b) => a + b;
const memoAdd = memoize(add);
console.log(memoAdd(2,3)); // => Calculating result 5
console.log(memoAdd(2,3)); // => Fetching from cache 5

Or we can change add the function:

const add = memoize((a, b) => a + b);
console.log(add(2,3)); // => Calculating result 5
console.log(add(2,3)); // => Fetching from cache 5

You want to see the performance boost in action? Take a look at this example below.

// recursive fibonacci function
const fibonacci = (n) => {
  if (n === 0 || n === 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

This fibonacci function takes a number, the position number of the Fibonacci sequence, and calculates the corresponding value. Since it’s recursive, it tends to get slower if the position you set gets higher. Lets go nuts here and test it with the 50th element on the sequence, shall we?

console.log(fibonacci(50)); // Call the function and go for a walk!

It took nearly 4 minutes to run the code. The recursive function must be called over 40 billion times (40,730,022,147 times to be specific)! It’s pretty insane.

Now lets memoize it. Since the fibonacci is a recursive function, we can not achieve this by creating a new memoized function, like the code below.

const memoFibonacci = memoize(fibonacci)
console.log(memoFibonacci(50)) // insane amount of time

This happens because we are only memoizing the first call. All subsequent recursive calls to fibonacci are not memoized. The only way to memoize recursive functions is by wrapping the main function with the memoize.

// recursive and memoized fibonacci function
const fibonacci = memoize((n) => {
  if (n === 0 || n === 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
})

console.log(fibonacci(50)) // runs fast!

Now it runs in less than one second and the results are exactly the same. Amazing! As you can see in the console, a lot os the calls are cached, preventing billions of recursive calls.

Is memoization same as caching?

Yes, kind of. Memoization is actually a specific type of caching. While caching can refer in general to any storing technique for future use, memoizing specifically involves caching the return values of a function.

Careful

Keep in mind that memoization does not make sense for all function calls. It does not work well for functions that are not pure, that is functions that have side effects. Memoizing only allows us to cache a result, so any other side effects get lost on successive calls. That said, you can get around this constraint, by returning a function that includes your side effects that you will need to execute after getting the result.

Also, there is a higher memory overhead since we must store our cached results so that we can later recall them as well as an added complexity of using memoization, so it really only makes sense for functions that are computationally expensive.