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.

`var = {}; = {}`

`$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)`

.

Log In