Fast Fibonacci – Memoization

def fibonacci(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

You may notice that the recursive Fibonacci algorithm closely resembles the mathematical equation. It has a logical clarity and elegance. Unfortunately, computing Fibonacci numbers this way becomes very slow as n grows larger. This is because the algorithm ends up recalculating the same numbers over and over again.

Even in a simple case like finding the Fibonacci number for n = 5, you can already see this waste:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1)
│   │   │   └── fib(0)
│   │   └── fib(1)
│   └── fib(2)
│       ├── fib(1)
│       └── fib(0)
└── fib(3)
    ├── fib(2)
    │   ├── fib(1)
    │   └── fib(0)
    └── fib(1)

Look at the repetition of fib(3) and fib(2)! That's what we can avoid with DP.

We've been tasked with building an interview question because Mappy is hiring developers! We need to build a fast Fibonacci function so that we can then ask candidates to do the same in their interview and compare their results to ours. Mappy needs backend engineers that understand the performance gains that can be attained with dynamic programming.

Alter the fibonacci function to be much faster using memoization.

We'll start by solving the problem in the normal manner, but we'll save our computations and use the stored answers where possible. This process of saving work is called memoization.

1. If n doesn't already have an entry in the memo dictionary, compute the result the same way you would using the slow method. However, instead of returning the result, add it to the memo dictionary. Be sure to pass the modified memo dictionary into the recursive calls.
2. Return the relevant entry in the memo dictionary.