Tracing Recursive Calls with the Call Stack

What is a Stack?

Before we can understand the call stack, we first need to understand what a stack is in general. It's one of the simplest data structures in computer science.

To summarize, a stack is a LIFO (Last-In, First-Out) data structure. Think of it like a stack of plates:

• You push a new plate onto the top of the stack.
• You pop a plate off the top to use it.
  You can only interact with the topmost item. The last plate you added is the first one you take off.

How Programs Use Stacks: The Call Stack

Your computer uses a stack internally to manage function calls. This is known as the call stack. Every time a function is called, the computer creates a package of information called a stack frame and pushes it onto the call stack.

This frame contains important details for that specific function call, including:

• The function's local variables (including its parameters).
• The "return address"—where in the code to resume after the function finishes.

Let's watch a video that illustrates this process with a brilliant analogy.

As the video showed, when a() calls b(), and b() calls c(), the stack looks like this:

c() must finish and return first (it's popped off the stack). Then b() can finish, and finally a().

A crucial point is that each stack frame holds its own set of local variables. This is why two different function calls can have a local variable named spam without interfering with each other—they exist in separate frames on the call stack.

The Call Stack in Recursion

So, what does this have to do with recursion? A recursive call is still just a function call. The only difference is that the function is calling itself. Each time it does, a new stack frame with its own local variables is pushed onto the call stack.

This also explains a common error in recursion: the stack overflow. If your recursive function never hits its base case, it will keep calling itself, pushing more and more frames onto the stack until the computer runs out of memory for the stack. To prevent this, Python stops the program and raises a RecursionError.

Tracing Factorial on the Call Stack

Let's apply this to our factorial function from the last lesson. We'll trace factorial(4). The following video provides a brilliant, step-by-step visualization of this process, building a diagram of the call stack as it grows and shrinks.

The process you just watched has two distinct phases:

1. Winding: The function calls itself repeatedly, pushing new frames onto the stack until the base case is reached. No calculations are completed during this phase; they are all left pending.
   • factorial(4) is called. It needs factorial(3).
   • factorial(3) is called. It needs factorial(2).
   • factorial(2) is called. It needs factorial(1).
2. Unwinding: Once the base case returns a value, the stack frames are popped one by one. Each frame uses the returned value from the call above it to complete its own calculation and return its result to the frame below.
   • factorial(1) returns 1.
   • factorial(2) receives 1, calculates 2 * 1, and returns 2.
   • factorial(3) receives 2, calculates 3 * 2, and returns 6.
   • factorial(4) receives 6, calculates 4 * 6, and returns 24.

This "winding" and "unwinding" is the fundamental execution pattern of most recursive functions.

Tracing a Non-Mathematical Example: String Reversal

The call stack works the same way for any type of data. Let's look at a function that recursively reverses a string.

Here's the Python code. See if you can apply the "recursive leap of faith":

• Base Case: Reversing an empty string gives you an empty string.
• Recursive Step: To reverse "hello", we can trust that our function can reverse "ello" to get "olle". Then we just need to stick the "h" on the end.

def reverse_string(s):



    # Base Case
    if len(s) == 0:
        return ""



    # Recursive Step
    else:



        # Recursively reverse the rest of the string (s[1:])
        reversed_substring = reverse_string(s[1:])



        # Add the first character (s[0]) to the end
        return reversed_substring + s[0]

print(reverse_string("hello")) # Output: olleh

Now, let's watch an animation that traces reverse_string("hello") on the call stack.

Your Turn: Tracing countDownAndUp

Let's solidify your understanding with a final example. This function is interesting because it has code that runs after the recursive call.

def count_down_and_up(number):
    print(number) # Code before the recursive call

    if number == 0:



        # Base Case
        print("Reached the base case.")
        return
    else:



        # Recursive Step
        count_down_and_up(number - 1)
    



    # This code runs AFTER the recursive call above has completely finished!
    print(f"{number} returning")

count_down_and_up(3)

Before you look at the answer, take a piece of paper and try to trace the execution of count_down_and_up(3). Use what you know about the call stack. What do you predict the output will be?

...

Here is the actual output:

3
2
1
0
Reached the base case.
1 returning
2 returning
3 returning

Let's trace why this happens:

1. count_down_and_up(3) is called. It prints 3 and then calls count_down_and_up(2). It now waits.
2. count_down_and_up(2) is called. It prints 2 and then calls count_down_and_up(1). It waits.
3. count_down_and_up(1) is called. It prints 1 and then calls count_down_and_up(0). It waits.
4. count_down_and_up(0) is called. It prints 0, then prints "Reached the base case." and returns. Its frame is popped.
5. Execution returns to the count_down_and_up(1) frame. It has finished its recursive call, so it now executes the code after the call: print("1 returning"). It then returns. Its frame is popped.
6. Execution returns to the count_down_and_up(2) frame. It prints 2 returning and returns. Its frame is popped.
7. Execution returns to the count_down_and_up(3) frame. It prints 3 returning and returns. The program is finished.

This example perfectly demonstrates that when a function call returns, execution picks up exactly where it left off in the calling function.

Conclusion

Fantastic work today! You've tackled the most critical concept for truly understanding recursion. By visualizing the call stack, you can demystify the "magic" and see the logical, step-by-step process the computer follows.

Key Takeaways:

• The call stack is a LIFO (Last-In, First-Out) data structure that programs use to manage function calls.
• Each function call pushes a stack frame onto the stack, containing its own local variables and a return address.
• In recursion, each self-call adds a new frame, causing the stack to wind.
• When the base case is hit, the stack begins to unwind as frames are popped, values are returned, and pending calculations are completed.
• A stack overflow (RecursionError) occurs when the stack grows too large, usually because a base case is never reached.

Preview of the Next Lesson:
Now that we can implement and trace recursive functions, we need to think about their performance. In the next lesson, we will analyze the exponential time complexity of a naive recursive Fibonacci function. You'll see that while recursion can be elegant, a naive implementation can be incredibly inefficient, which will set the stage for learning about algorithm analysis and optimization techniques.