# 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);
});```

Get JavaScript: The Good Parts now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.