Log In

While the previous recursive solution works correctly, it is very inefficient.

The recursive subproblems are called over and over again.

For example, let's visualize fibonacci(5) making its recursive calls as a tree.

As you can see, fibonacci(3) and fibonacci(2) are called multiple times.

As the input gets larger, this gets more inefficient. When fibonacci(30) is called, fibonacci(2) is called over half a million times.

In order to make the function much faster, we can record the results that we have, so we only have to calculate a subproblem once.

This is called memoization. The name comes from taking the "memo" of a result, and referring back to it later.

We could make an object that stores the previous results. This object (also known as a cache) could be global and outside of the function. If we wanted to make the function not have side effects, another way is to pass the object as a parameter in recursive calls.

$results = {}

Any time we get to the end of a function calling fibonacci(n), we would run something like:

results[n] = valueToReturn;results[n] = value_to_return$results[n] = value_to_return

In the beginning of the function, we would check to see if we have already stored that value, and return it if so.

if (results[n] !== undefined) {
  return results[n];
}
if n in results:
  return results[n]
if $results.include?(n)
  return $results[n]

Please create a modified version of fibonacci with memoization. It should be able to handle fibonacci(70).

Sign Up or Log In to access the code editor and answer the question!
Log In