JavaScript: The Good Parts

Memoization

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

Let's say we want a recursive function to compute Fibonacci numbers. A Fibonacci number is the sum of the two previous Fibonacci numbers. The first two are 0 and 1:

var fibonacci = function (n) {
    return n < 2 ? n : fibonacci(n − 1) + fibonacci(n − 2);
};

for (var i = 0; i <= 10; i += 1) {
    document.writeln('// ' + i + ': ' + fibonacci(i));
}

// 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 unnecessary work. The fibonacci function is called 453 times. We call it 11 times, and it calls itself 442 times in computing values that were probably already recently computed. If we memoize the function, we can significantly reduce its workload.

We will keep our memoized results in a memo 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 fibonacci = (function (  ) {
    var memo = [0, 1];
    var fib = function (n) {
        var result = memo[n];
        if (typeof result !== 'number') {
            result = fib(n − 1) + fib(n − 2);
            memo[n] = result;
        }
        return result;
    };
    return fib;
}( ));

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 memoizer function will take an initial memo array and the formula function. It returns a recur function that manages the memo store and that calls the formula function as needed. We pass the recur function and the function's parameters to the formula function:

var memoizer = function (memo, formula) {
    var recur = function (n) {
        var result = memo[n];
        if (typeof result !== 'number') {
            result = formula(recur, n);
            memo[n] = result;
        }
        return result;
    };
    return recur;
};

We can now define fibonacci with the memoizer, providing the initial memo array and formula function:

var fibonacci = memoizer([0, 1], function (recur, n) {
    return recur(n − 1) + recur(n − 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 factorial = memoizer([1, 1], function (recur, n) {
    return n * recur(n − 1);
});