JavaScript Memoization: Optimizing Recursion

Recursive functions recalculate the same values over and over. Memoization caches results by index so fibonacci(n) is only computed once — a small change with a significant impact on recursive performance.

I first came across the concept of memoization in Douglas Crockford's Javascript: The Good Parts, and again in Nicholas Zakas' High Performance JavaScript.

It is a technique used in optimizing recursive functions, such as calculating factorial or Fibonacci numbers.

Recursive Functions

A recursive Fibonacci function might look like this:

JavaScript

function fibonacci(n) {
  if (n < 2)
    return n;
  return fibonacci(n-1) + fibonacci(n-2);
}

Or, more concisely:

JavaScript

function fibonacci(n) {
  return n < 2 ? n : fibonacci(n-1) + fibonacci(n-2)
}

A recursive function needlessly performs the same calculations over and over; we can prevent these unnecessary calculations by caching the results. We can implement a cache as either an array or a JavaScript object, and the value stored at n will correspond to fibonacci(n).

Memoizing

Update the function to include a property called cache so that cache[n] stores the value for fibonacci(n).

JavaScript

function fibonacci(n) {
  if (!fibonacci.cache) {
    fibonacci.cache = [0,1]; 
  }
  if (isNaN(fibonacci.cache[n])) {
    fibonacci.cache[n] = fibonacci(n-1) + fibonacci(n-2);
  }
  return fibonacci.cache[n];
};

We first check if a cache exists; if not, we need to create one and populate it with the seed values.

When fibonacci(n) is called, we check fibonacci.cache to see if a value exists at the index n; only if it doesn't exist would we recursively call fibonacci(n-1) and fibonacci(n-2), and update the value of fibonacci.cache[n].

Cache Data Type

In the previous example we used an array to represent the cache. We could have also defined the cache as an object:

JavaScript

fibonacci.cache = {
  "0": 0,
  "1": 1
};

In that case, we check to see if our cache has a value for n with:

JavaScript

if( !fibonacci.cache.hasOwnProperty(n) )