How does a baby pronounce Memorization? Memoization!
Tags: computerscience, javascript, functional, closures
Published: 2020-11-21 01:18:03

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:
```javascript
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`
```javascript
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:
```javascript
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:
```javascript
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!