Introduction

In this post, I'll walk through implementing the Fibonacci sequence in JavaScript, and then improving the approach by memoizing previous returns from the function. You can think of memoizing like implementing a 'cache' which stores information from previous calls to a function. In JavaScript, the best approach to take advantage of closures and implement an outer function, which creates the cache as a map, and an inner function, which inherits the scope of the outer function and can write/read from the cache.

1: Recursive Fibonacci

Reviewing recursion is outside the scope of this post, but I wanted to share this approach with you as the memoize function will incorporate this code. This approach to fibonacci solves in O(log n) run time.

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

2: Memoize Fibonacci

Memoizing the recursive function above will make a tradeoff between speed and space. Implementing the cache will take O(n) space complexity, but the best case for the solution will become O(1) instead of O(log n).

There are degrees of increasing utility (or, intelligence) to memoizing the fibonacci function.

1. Only cache answers for a given n, e.g. fib(20) would not benefit from previous calls of fib(21) or fib(19)
2. Cache all solutions up to a given n, e.g. fib(20) should cache fib(1...20), but fib(21) doesn't take advantage of fib(20)
3. Given an n greater than a previous n, leverage the solution for the previous greatest n, e.g. fib(21) should leverage fib(20)

The approach I implement below is the latter of the three. It 'caches' all previous solutions to the fibonacci function, including the recursive calls. So, memoizeFib(5) will cache the fibonacci number that corresponds to (1...5).

const memoizeFib = (n) => {
  const cache = {};
  const fibonacci = (n) => {
    if (cache[n]) {
      return cache[n];
    }

    if (n < 3) {
      cache[n] = n - 1;
      return n - 1;
    }

    let solution = fibonacci(n - 1) + fibonacci(n - 2);
    cache[n] = solution;
    return solution;
  };
  return fibonacci;
};

You would call this code by creating an instance of the memoizeFib function (which creates the cache and returns the fibonacci function), and passing that instance an argument. Example:

const memoizedFib = memoizeFib()
memoizedFib(5) // returns 3

Conclusion

Closures and memoizing in JavaScript are not only used to improve performance and prevent repetitious, expensive work. They're used for data security and privacy. Consider that, for the above example, the cache for memoizedFib is not accessible outside the scope of memoizedFib.

If you want to play around with the code above, you can fork the solution I implemented (with tests) on CodePen here.