Memoization. Improving Recursive Solution for Fibonacci Sequence Problem.

3 min readApr 30, 2018

My recent blog post on Fibonacci sequence covered an iterative and recursive approaches to solving this common interview challenge. As a reminder, the challenge sounded like this: “Write a function to return an n element in Fibonacci sequence”.

After looking at time complexity for both solutions it was concluded that the recursive solution was getting significantly slower for each additional number in the sequence due to exponential time growth. There is, however, a smart way of improving this solution and that is using Memoization.

“Memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.” (Wikipedia)

For our recursive solution we want to store the arguments of each function call as well as function’s output, and reuse it later on if the function was called with the same arguments.

Our recursive solution looked like this:

function fib(n) {
  if (n < 2) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}

Let’s define our memoize function. It will receive a function as an argument and also return a function. We will also create an empty object that will actually store function calls for us.

function memoize(fn){
  const cache = {}
  return function(){
  }
}

The function that is returned in memoize needs to receive the same argument n as the ones we’d pass to fib. However if we were to write a reusable memoizer that can be applied to functions other that fib, we would want to allow it to receive any number of arguments like so:

function memoize(fn){
  const cache = {}
  return function(...args){
  }
}

From here we will need to look into our memory bank, our cache constant, and if it contains a key with this set of arguments, we will return the corresponding value.

function memoize(fn){
  const cache = {}
  return function(...args){
    if (cache[args]){
      return cache[args];
    }
  }
}

If the function has never been called with the current set of arguments we will have to pass them to the original “slow” function that is the fn passed to memoize as an argument and then save the result to cache. In order to pass an array of arguments we need to use apply() method.

function memoize(fn){
  const cache = {}
  return function(...args){
    if (cache[args]){
      return cache[args];
    }
    newCall = fn.apply(null, args);
    cache[args] = newCall;
    return newCall;
  }
}

To use memoize function for our Fibonacci problem we simply store memoize function call as a constant and pass arguments that would otherwise be passed to fib to this constant.

const fastFib = memoize(fib);

And, finally, we need to make sure that when fib performs recursive calls, it calls the new fast version of itself rather than the original self.

const fastFib = memoize(fib);function fib(n) {
  if (n < 2) {
    return n;
  }
  return fastFib(n - 1) + fastFib(n - 2);
}

And that’s it! We have significantly improved the time that it will take recursive solution to run for large numbers, as it will not be growing exponentially anymore.

The memoizer that was written here is pretty universal and can be used to improve runtime for basically any function.

As always, thanks for reading and happy coding!

Memoization. Improving Recursive Solution for Fibonacci Sequence Problem.

Written by Lucya Koroleva