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).