Nov 14 2022 by Chris Lyons

Implementing Memoization in a Recursive Fibonacci Sequence Function

Below is a recursive fibonacci sequence function with no memoization implementation. It runs very slowly and can be massively improved.

fibonacci.js

const fibonacci = n => {
if(n < 2) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}

You can test the speed with the following code:

console.time();
console.log(fibonacci(999));
console.timeEnd();

Spoiler alert: it’s very slow.

Enter Memoization

The following shows how to implement memoization to greatly increase the function’s speed:

fibonacciMemoized.js

// First we create a variable to act as our cache.
const cache = [];
const fibonacci = n => {
if(n < 2) return 1;
// Then we check to see if we've already stored a result
// for `n` in our cache. If we have, we return it.
if(cache[n]) return cache[n];
// And if we haven't cached this number yet, we cache it and return it
return cache[n] = fibonacci(n - 1) + fibonacci(n - 2);
}

You can test the speed with the following code:

// First time will be considerably faster than the
// version without memoization.
console.time();
console.log(fibonacci(999));
console.timeEnd();
// Second time finishes WAY faster than even the improved
// times seen with the first call above.
console.time();
console.log(fibonacci(999));
console.timeEnd();

Final Code (Sans Comments)

fibonacciMemoized.js

const cache = [];
const fibonacci = n => {
if(n < 2) return 1;
if(cache[n]) return cache[n];
return cache[n] = fibonacci(n - 1) + fibonacci(n - 2);
}

There you have it. Now go ace that technical interview!