Memoize like a boss (part 2)

Memoization is fun and if you read my previous post you should have fair idea of how memoization can be easily implemented in JavaScript. Previous examples were using very simple function and now you might wonder how to deal with recursion and still get all the benefits. Last time around we end up with:

Function.prototype.memoized = function(a) {
if (typeof this.cache === "undefined") this.cache = [];
if (this.cache[a]) {
return this.cache[a];
} else {
this.cache[a] = this(a);
return this.cache[a];
}
}

Function.prototype.memoize = function() {
var t = this;
return function() {
return t.memoized.apply(t, arguments);
}
}

myTest = (function superLongCalculation(someArg) {
    return someArg * 3;
}).memoize();

console.log(myTest(2));

So to recap.. myTest function once called will call memoized method on original function object t:

t.memoized.apply(t, arguments);

memoized method will do the check if the value for argument ("2" in our example) has already been precalculated and if so will returned whatever is stored in cache. Otherwise will call original function, do the magic and return new value. If this doesn't quite make sense have a look at my original post where I went into details of my basic memoization implementation.

So now you might wonder what will happen if instead of something overly simple as above we will use recursive function to do the work. Calculating fibonacci numbers seems to be "Hello World" of memoization and so lets plug this thing into our memoization code:

Function.prototype.memoized = function(a) {
if (typeof this.cache === "undefined") this.cache = [];
if (this.cache[a]) {
return this.cache[a];
} else {
this.cache[a] = this(a);
return this.cache[a];
}
}

Function.prototype.memoize = function() {
var t = this;
return function() {
return t.memoized.apply(t, arguments);
}
}

myTest = (function fibonacci(n) {
return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}).memoize();

console.log(myTest(2));

Works like a charm. Returns correct values, however we can make it better. It still does unnecessary work and given our current code there is easy way to improve it.

Notice how the fibonacci function object itself is memoized, however internal calls to itself are not. This means that in this case we do half-assed optimization only and anything half-assed is not cool. Lucky for us the Function object has memoized method already that we can directly call as in the very first examples in part one:

Function.prototype.memoized = function(a) {
if (typeof this.cache === "undefined") this.cache = [];
if (this.cache[a]) {
return this.cache[a];
} else {
this.cache[a] = this(a);
return this.cache[a];
}
}

Function.prototype.memoize = function() {
var t = this;
return function() {
return t.memoized.apply(t, arguments); }

}

myTest = (function fibonacci(n) {
return n < 2 ? n : fibonacci.memoized(n - 1) + fibonacci.memoized(n - 2);
}).memoize();

console.log(myTest(2));

I also put few tests that are available here so you can see the difference. I also realise that there are other, more efficient ways of calculating fibonacci numbers, I believe however that examples above are simple enough to see how memoization can be used with recursive functions.