Fibo and Memo

A common theme in dynamic programming algorithm questions on Leetcode or in job interviews, is that the underlying problem is some twist on or manipulation of the numbers of the Fibonacci sequence. The Fibonacci sequence is a series of numbers where the next number is the sum of the previous two. Normally it starts at 0,1 followed by 1,2,3,5,8,13,21 and so on. To find the nth number of a Fibonacci sequence, we can use a for loop to sum it up iteratively using something like the following:

const fib = (n) => {
  if (n === 1) return 0;
  let prevprev;
  let prev = 0;
  let fibNumber = 1;
  for (let i = 2; i < n; i++) {
    prevprev = prev;
    prev = fibNumber;
    fibNumber = prevprev + prev;
  }
  return fibNumber;
}

This will return the nth Fibonacci number in O(n) time complexity and is a valid solution. But what if you were asked to solve it recursively?

Recursive Fibonacci

The most basic recursive way to solve for the nth Fibonacci number is to keep on making recursive calls to find the previous two numbers in the series until we hit the stopping point of fib(1) or fib(2) as we know those are our two starting numbers of 0 and 1. The code for this would look something like the following :

const fib = (n) => {
  if (n === 1) return 0;
  if (n === 2) return 1;
  return fib(n-1) + fib(n-2);
}

This returns our nth Fibonacci number, however if we test this on larger numbers you might notice that the computer starts having to take longer and longer as our number n increases. This is because this solution is essentially creating a tree and as n grows the tree grows at an exponential rate. Below is an example of what the tree would look like if we were solving for the 7th digit of the Fibonacci sequence which is already fairly large:

https://stackoverflow.com/questions/35959100/explanation-on-fibonacci-recursion

Looking at a picture of the tree, you may notice that there are a lot of things that are repeated. I’ve highlighted below parts of the tree we are checking more than once that we know will always be the same:

If there was a way that we could remember the values we’ve already seen as we traverse the tree, we could save ourselves a lot of work. Enter memoization.

Memoization

Memoization, or memo for short, is a technique we can use to store certain values as we go to save ourselves from going down paths we already know the answer to. To add memoization to the recursive code we have above, we need to add an object to our recursion to store the values we’ve discovered. This only requires a couple extra lines of code but saves us a tremendous amount of runtime.

const fib = (n, memo ={}) => {
  if (n === 1) return 0;
  if (n === 2) return 1;
  if (n in memo) return memo[n];
  memo[n] = fib(n-1, memo) + fib(n-2, memo);
  return memo[n];
}

Instead of our recursion only checking if it is reaching the bottom nodes of the tree, it also now checks if we have the value of the current node already stored in our memo object. If we were to redraw our tree into the nodes that are visited with memo it would look a lot cleaner:

Notice how now we only have n-1 + n-2 nodes to check. This brings our time complexity back down to O(n), the same as our iterative solution. Memoization can be a very powerful tool when dealing with trees, even trees not based on the Fibonacci sequence as long as we know that the value at similar nodes will always be the same.