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

Become a Member to join the conversation.