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.

01:15 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.

01:54 If so, then you return that number. 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.