For more information on concepts covered in this lesson, you can check out Thonny: The Beginner-Friendly Python Editor.
Visualizing the Memoized 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: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.
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.
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.
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: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.
Become a Member to join the conversation.