How does a baby pronounce Memorization? Memoization!

#computerscience #javascript #functional #closures

Memoization is a concept of computation in which common results are stored, or cached, to avoid re-calculation. This is extremely useful when an algorithm has an increasing number of similarly computed branches. Let's dive into a common example with Javascript, with the recursive Fibonacci sequence.

Here's a simple recursive Fib:

const fib = (n) => {
  if (n < 2) return n;

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

The big O of this algorithm evaluates to O(2^n). Hopefully we can all agree - this is abysmal.

Let's evaluate the line return fib(n - 1) + fib(n - 2);. At every recursive call, we are now branching down into two more Fib calls; and so on and so on. However, Fib looks backwards at itself: n-1 and n-2. Which means there will be many recursive Fib's which want to calculate the same thing. If we leave them to their devices, the call stack could easily be overwhelmed, and even for relatively small n, computation will take a long time (try fib(50)).

This is where memoization comes in. It allows us to avoid every recursive Fib call from branching into clones like something out of the Matrix movies. How? By caching the result when we've already found the answer the first time. That way, when another branch wants to calculate a fib(k) for some k > 2, we don't have to keep climbing the call stack with two more subsequent Fibs - we could return early with a concrete result.

Let's build our memoization function, we'll call it memo

const memo = (funcToMemo) => {
  const cache = {};

  // Return a new function that is memoized
  return function(...args) {
    // We've computed this already!
    if (cache[args]) return cache[args];

    // Never seen it? Compute it, but store it after
    const result = funcToMemo(...args);
    cache[args] = result;

    return result;
  }
}

Javascript treats functions as first-class citizens, so we can utilize closures that allow us to build this memoization function. I'd suggest reading up on closures and first-class functions if you're unfamiliar.

The memo function passes a cache object to an anonymous function which is now able to store, collect, and retain that information through recursive calls.

Now that we have this closure-enabled memoization function. We can wrap it around our fib function. However, due to how memory and naming is aligned, we have to sync it with the proper function names. Let's assume we want to call our memoized fib memoFib. We can do that easily with:

const memoFib = memo(fib);

However, since the fib function recursively calls the fib function itself, it will lose scope on the memoFib, and won't know about its brand new, speedy self. To really make this work, we have to update the recursive call with the anticipated memoized function name:

const fib = (n) => {
  if (n < 2) return n;

  // Recursively call the fast memoized fib
  return memoFib(n - 1) + memoFib(n - 2);
}

const memoFib = memo(fib);

And we're done! With a little proactive coding, we can call some insanely large fib numbers we would otherwise not be able to run at all. Try this with something like memoFib(500) - the number is massive, and computed fast!