# Speed up recursive functions with memoization

Fibonacci sequence is very familiar to everybody. We can write the following function in 20 seconds.

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

It works, but is not efficient. It did lots of duplicate computing works, we can cache its previously computed results to speed it up.

```
var fibonacci = (function() {
var cache = [0, 1]; // cache the value at the n index
return function(n) {
if (cache[n] === undefined) {
for (var i = cache.length; i <= n; ++i) {
cache[i] = cache[i - 1] + cache[i - 2];
}
}
return cache[n];
}
})();
```

Also, we can define a higher-order function that accepts a function as its argument and returns a memoized version of the function.

```
var memoize = function(func) {
var cache = {};
return function() {
var key = JSON.stringify(Array.prototype.slice.call(arguments));
return key in cache ? cache[key] : (cache[key] = func.apply(this, arguments));
}
}
fibonacci = memoize(fibonacci);
```

And this is an ES6 version of the memoize function.

```
var memoize = function(func) {
const cache = {};
return (...args) => {
const key = JSON.stringify(args);
return key in cache ? cache[key] : (cache[key] = func(...args));
}
}
fibonacci = memoize(fibonacci);
```

we can use `memoize()`

in many other situations

- GCD(Greatest Common Divisor)

```
var gcd = memoize(function(a, b) {
var t;
if (a < b) t = b, b = a, a = t;
while (b != 0) t = b, b = a % b, a = t;
return a;
});
gcd(27, 183); //=> 3
```

- Factorial calculation

```
var factorial = memoize(function(n) {
return (n <= 1) ? 1 : n * factorial(n - 1);
})
factorial(5); //=> 120
```

Learn more about memoization:

Five years worth of JavaScript that you can learn in just a few weeks. This is the most complete and efficient flashcards ever created.

GET THE CARDS NOWUse the 100 answers in this short book to boost your confidence and skills to ace the interviews at your favorite companies like Twitter, Google and Netflix.

GET THE BOOK NOW