After my last post where I described some recursion basics with JavaScript, I thought it would be fun to get into a slightly more advanced topic: Memoization.

You can read that article, but the basic concept of memoization is not repeating calculations if you've already found the answer. The example used there is finding factorials (5! = 5 * 4 * 3 * 2 * 1), but that only works if you call the function multiple times in your program. I want to talk about those rare cases where memoization comes in handy within the function itself.

Fibonacci Sequence

You've probably heard about this sequence before - it's the one followed by pine cones and the golden ratio. It starts 0, 1, 1, 2, 3, 5, 8, 13... where each number is the sum of the two previous numbers.

Based on that description, you can probably guess if we wanted to calculate the nth fibonacci number, recursion would come in handy. The first pass looks like this in JavaScript:

function fibonacci(positiveInteger) {
    if (positiveInteger === 1) {
        return 1;
    } else if (positiveInteger === 0) {
        return 0;
    } else {
        return fibonacci(positiveInteger - 2) + fibonacci(positiveInteger - 1);
    }
}

Makes sense? You build in some automatic returns for 0 and 1 and then it works as expected with the answer being the sum of the two previous fibonacci numbers.

The problem

It works great! The problem, though, lies in trying to calculate larger numbers. Running node in the terminal on my Chromebook starts getting slow around fibonacci(30) and fibonacci(100) appears to completely crash my terminal. I suspect it would stop running at some point, but I don't want to wait all day.

The solution - Memoization

As you probably guessed, we can use memoization to improve this behavior. How? Each time we calculate a fibonacci number using the above function, we were calculating all the fibonacci numbers down to 0. This involves a lot of repeated calculations. Let's try to remember all the fibonacci numbers we've calculated and pass them into the recursive calls.

function fibonacci(positiveInteger, foundFibonaccis) {
    if (typeof(foundFibonaccis) === 'undefined') {
        var found = { 0: 0, 1: 1 };
    } else {
        var found = foundFibonaccis;
    }
    if (typeof(found[positiveInteger]) !== 'undefined') {
        return found[positiveInteger];
    } else {
        found[positiveInteger] = fibonacci(positiveInteger - 2, found) + fibonacci(positiveInteger - 1, found);
    }
    return found[positiveInteger];
}

Now we are storing each calculated number in an object and passing it into future recursive calls. If nothing is passed in, I set the object to { 0: 0, 1: 1 } much like I supplied the answers for 0 and 1 in the first function.

Does that improve the performance? Oh yeah! On my Chromebook I now get the answer for fibonacci(1000) almost instantly. In fact, I get the answer up to fibonacci(1476) right away and the only reason I can't calculate higher fibonacci numbers is that JavaScript can't handle it and starts returning Infinity.

I hope you found this mini introduction to memoization helpful. If you've found other areas where memoization would be helpful let me know!