Memoizing the Recursive Algorithm

00:00 Memoizing the Recursive Algorithm. As you saw in the code earlier on, the Fibonacci function calls itself several times with the same input. Instead of a new call every time, you can store the results of previous calls in something like a memory cache.

00:18 You can use a Python list or dictionary to store the results of previous computations. This technique is called memoization.

00:28 Memoization speeds up the execution of expensive recursive functions by storing previously calculated results in a cache. This way, when the same input occurs again, the function just has to look up the corresponding result and return it without having to run the computation again.

00:45 You can refer to these results as cached or memoized. With memoization, you just have to traverse up the call tree of depth N once after returning from the base case, as you retrieve all the previously calculated values highlighted in yellow, F(2) and F(3), from the cache earlier.

01:04 The orange path shows that no input to the Fibonacci function is called more than once. This significantly reduces the time complexity of the algorithm from exponential to linear. Even for the base cases, you can replace calling F(0) and F(1) with just retrieving the values directly from the cache indices zero and one.

01:25 So you end up calling the function just six times instead of fifteen.

01:30 On-screen, you’ll see a possible translation of this optimization into Python code. In this example, you use a Python dictionary to cache the computed Fibonacci numbers.

01:41 Initially, the cache contains the starting values of the Fibonacci sequence, 0 and 1. Inside the function, you first check if the Fibonacci number for the current input is already in the cache. If so, then you return that number.

01:58 If there’s no Fibonacci number for the current value of n, then you compute it by calling fibonacci_of() recursively and updating the cache.

02:07 The final step is to return the requested Fibonacci number.

02:20 On-screen, you can see some typical timings of the original algorithm and the memoized version.

02:27 In the next section, we’ll look at an alternative way to optimize generation of the Fibonacci sequence by taking a different approach.