Memoization In Javascript

Definition: Functions can use objects to remember the results of previous operations, making it possible to avoid unnecessary work. This optimization is called memoization. JavaScripts's objects and arrays are very convenient for this.

Explanation: Let's say we want a recursive function to compute Fibonacci numbers. A basic example of generating the same is written below:

var fib = function(x){
    return x < 2 ? x : fib(x-1) + fib(x-2);
};

for(var a = 0; a <= 10; a++){
    console.log('--> ' + a + ' : ' + fib(a));
}

Output for the above-
--> 0: 0
--> 1 : 1
--> 2 : 1
--> 3 : 2
--> 4 : 3
--> 5 : 5
--> 6 : 8
--> 7 : 13
--> 8 : 21
--> 9 : 34
--> 10 : 55

This works, but it is doing a lot of unnecesary work. The fib function is called 453 times. We call it 11 times, and it calls itself 442 times in computing values that were probably already computed. If we memoize the function, we can significantly reduce its workload.

We will keep our memoized results in a "memoized" array that we can hide in a closure. When our function is called, it first looks to see if it already knows the result. If it does, it can immediately return it:

var fib = function(){
    var memoized = [0,1];
    var f = function(x){
        var res = memoized[x];
        if(typeof res !== 'number'){
            res = f(x-1) + f(x-2);
            memoized[x] = res;
        }
        return res;
    };
        return f;
}();

This function returns the same results, but it is called only 29 times. We called it 11 times. It called itself 18 times to obtain the previously memoized results.

We can generalize this by making a function that helps us make memoized functions. The "memo" function will take an intial "m" array and the "basic" function. It returns a "final" function that manages the m store and that calls the basic function as needed. We pass the final function and the function's parameters to the basic function.

var memo = function(m, basic){
    var final = function(x){
        var res = m[x];
        if(typeof res !== 'number'){
            res = basic(final, x);
        }
        return res;
    };
    return final;
};

We can now define fib with the memo, providing the intial m array and basic function:

var fib = memo([0,1], function(final, x)){
    return final(x-1) + final(x-2);
};

By devising functions that produce other functions, we can significantly reduce the amount of work we have to do. For example, to produce a memoizing factorial function, we only need to supply the basic factorial formula:

var fact = memo([1,1], function(basic, x)){
    return x * basic(x-1);
};