Visualizing the Memoized Sequence Algorithm

00:00 Visualizing the Memoized Fibonacci Sequence Algorithm.

00:05 You can effectively understand how each call to a recursive Fibonacci function is handled using a call stack representation. The way each call is pushed onto the stack and popped off reflects exactly how the program runs.

00:19 It clearly demonstrates how calculating large numbers will take a long time if you don’t optimize the algorithm. In a call stack, whenever a function returns a result, a stack frame representing the function call is popped off of the stack.

00:35 Whenever you call a function, you add a new stack frame to the top of the stack. In general, this operation has a space complexity of O(N) because there are no more than N stack frames on the call at a single time.

00:50 There’s a beginner-friendly code editor called Thonny that allows you to visualize the call stack of a recursive function in a graphical way. You can check out this Real Python course to learn more.

01:03 To visualize the memoized recursive Fibonacci algorithm, you’ll use a set of diagrams representing the call stack. The step number is indicated by the blue label below each call stack.

01:15 Say you want to compute F(5). To do this, you first push the call to the function onto the call stack. To compute F(5), you must compute F(4), as outlined by their recurrence relation.

01:28 So you add that new function call to the stack. To compute F(4), you must compute F(3), so you add another function call to the stack. To compute F(3), you must compute F(2), so yet another function call is added to the stack. To compute F(2), you must compute F(1), so you add that to the stack.

01:50 As F(1) is a base case, it returns immediately with one, and you remove this call from the stack.

01:57 Now you start to unwind the results recursively. F(1) returns the result back to its calling function, F(2). To compute F(2), you also need to compute F(0).

02:08 You add F(0) to the stack. Since F(0) is a base case, it returns immediately, giving you zero. Now you can remove it from the call stack.

02:19 This result of calling F(0) is returned to F(2). Now you have what you need to compute F(2) and remove it from the stack. The result of F(2) is returned to its caller, F(3). F(3) also needs the results of F(1) to complete its calculation, so you add that back to the stack.

02:39 F(1) is a base case, and its value is available in the cache, so you can return a result immediately and remove F(1) from the stack.

02:48 You can now complete the calculation for F(3), which is two. You now remove F(3) from the stack after completing its calculation and return the result to its caller, F(4).

03:01 F(4) also needs the results of F(2) to compute its value. You push the call of F(2) onto the stack. This is where the cache comes in. You’ve already calculated it before, so you can just retrieve the value from the cache, avoiding a recursive call to compute the result of F(2) again.

03:19 The cache returns one, and you remove F(2) from the stack. F(2) is returned to its caller, and now F(4) has all it needs to compute its value, which is three.

03:30 Next, you remove F(4) from the stack and return its results to the final and original caller, F(5). F(5) now has the result of F(4) and needs the result of F(3).

03:42 You push an F(3) call onto the stack, and the cache comes into play again. You’ve previously calculated F(3), so all you need to do is to retrieve it from the cache.

03:52 There’s no recursive process to compute F(3). It returns two, and F(3) is removed from the stack. Now F(5) has all the values it needs to calculate its own value.

04:04 You get five by adding three and two, and that’s the final step before the F(5) call is popped off the stack. This action ends the sequence of recursive function calls.

04:15 The call stack is empty now. You’ve completed the final step to compute F(5).

04:22 Representing a recursive function call using a call stack diagram helps you understand all of the work that takes place behind the scenes. It also allows you to see how many resources a recursive function call can take up. Putting all these diagrams together allows you to visualize how the whole process looks.

04:40 You can take a closer look at the included course materials to zoom in on individual steps.

04:47 If you don’t cache previously computed Fibonacci numbers, some of the stack stages in this diagram would be much taller, which means they would take longer to return a result to their respective callers. In the next section of the course, we’ll take a different approach and use iteration and a Python function.