Memoization in JS

I've been re-sharpening my algorithm skills and thought I'd write a quick little article about memoization with Javascript. If you're not familiar with memoization, let me give you the quick n' dirty...

Rather than recompute and recompute and recompute the same values over again, as in the case of the Fibonacci sequence (recursively), we can store some of these values in a cache of sorts and simply check to see if we've calculated them before.

That's it. A very simple concept that can help immensely in trimming our run-times down. As an example, the forementioned recursive Fibonacci sequence has a run-time complexity of O(2^n), which is less-than-ideal. With memoization we can smack that down to O(n), which is muy bueno. It's not all puppies and kittens and rainbows though, there's still a space tradeoff, but generally we're not too concerned with space when we're talking about exponential run-times vs. linear run-times. Still though, it's something to think about nonetheless. So how do we implement the memoization technique in JS?

With Fibonacci it's as simple as...

function Fibonacci() {
  this.cache = [];
};

Fibonacci.prototype.getFib = function( i ) {
  // error handling...
  if( i < 0 ) {
    throw new Error('Non-negative integers only!');
  }
  // base cases...
  else if( i === 0 || i === 1 ) {
    return 1;
  }
  // check our cache to see if we've computed already...
  else if( this.cache[i] ) {
    return this.cache[i];
  }
  // Compute what we haven't yet...
  else {
    this.cache[i] = this.getFib( i - 1 ) + this.getFib( i - 2 );
    return this.cache[i];
  }
};

var fib = new Fibonacci();
fib.getFib(100); // 573147844013817200000

This returns immediately when I run it in JS Bin, but try running the standard recursive solution to the Fibonacci sequence in JS Bin and you'll just fry their servers. Looking again at the complexity I noted above we can see why: O(100) vs O(2^100).

So there you have it, a memoization example using this and prototypal inheritance. We get a nice, clean, Fibonacci object to play with, and each instantiation gets its own little cache. And because we attached the getFib function on the prototype chain the only real memory consideration we have to stress-out about is the cache size; there won't be multiple copies of the function floating around each time we instantiate a new Fibonacci object. Fantastic.