Tracing Recursive Function Calls

In our last couple of lessons, we've defined recursion and used it to build the powerful mergeSort algorithm. You even used printf statements to get a glimpse of the algorithm's execution flow. Today, we'll pull back the curtain and explore the fundamental mechanism that makes recursion possible: the call stack.

This lesson will demystify how your computer keeps track of nested and recursive function calls. By the end, you will be able to trace the execution of a simple recursive function like factorial, understanding exactly how memory is managed step-by-step. This knowledge is crucial not just for mastering recursion, but for debugging and understanding program execution in general.

1. The Engine of Function Calls: The Call Stack

Whenever you call a function in C, the system needs to save its current context—where it was in the main function, the values of local variables, etc.—so it can return and resume execution later. This is managed using a region of memory called the call stack.

The call stack works on a Last-In, First-Out (LIFO) principle. When a function is called, a stack frame (also called an activation record) is "pushed" onto the top of the stack. This frame is a dedicated block of memory for that specific call, containing:

• The function's parameters.
• The function's local variables.
• The return address (the location in the calling function to jump back to when this call is finished).

When the function finishes, its stack frame is "popped" off the stack, and execution returns to the stored return address. Recursion simply reuses this same mechanism, with a function calling itself.

To get a more formal understanding of this process, let's read an article that explains it in the context of C.

2. A Classic Example: The Factorial Function

The factorial function is a perfect, simple example for studying recursion. The factorial of a non-negative integer $n$, denoted as $n!$, is the product of all positive integers up to $n$.

Mathematically, it has a natural recursive definition:

• Recursive Step: $n!=n\times (n-1)!$ for $n>0$
• Base Case: $0!=1$

This translates directly into a C function:

int factorial(int n) {
    // Base Case
    if (n == 0) {
        return 1;
    }
    // Recursive Step
    else {
        return n * factorial(n - 1);
    }
}

Notice how the code mirrors the mathematical definition. The if (n == 0) block is our base case, which stops the recursion. The else block is the recursive step, where the function calls itself with a smaller version of the problem (n - 1).

3. Tracing Factorial on the Call Stack

Let's now trace what happens when we call factorial(4). We'll see frames being pushed onto the stack until we hit the base case, and then popped off as the results are calculated and returned.

The following video brilliantly illustrates this process. While it uses a slightly different function, fun(n), the principle of pushing and popping activation records on the stack is identical and exceptionally well explained.

Now, let's apply that same logic specifically to our factorial(4) call. The diagram below shows the state of the call stack at its deepest point.

Here is a step-by-step summary of the execution flow:

1. Pushing Phase (Winding):

   • main() calls factorial(4). A frame for factorial(4) is pushed. It must wait for the result of factorial(3).
   • factorial(4) calls factorial(3). A new frame is pushed. It must wait for factorial(2).
   • factorial(3) calls factorial(2). A new frame is pushed. It must wait for factorial(1).
   • factorial(2) calls factorial(1). A new frame is pushed. It must wait for factorial(0).
   • factorial(1) calls factorial(0). A new frame is pushed. The stack is now at its maximum depth for this call.

2. Base Case and Popping Phase (Unwinding):

   • Inside factorial(0), n is 0. The base case is met, and it returns 1. The factorial(0) frame is popped.
   • Control returns to factorial(1). It receives the value 1 and computes its return value: 1 * 1 = 1. The factorial(1) frame is popped.
   • Control returns to factorial(2). It receives 1 and computes 2 * 1 = 2. The factorial(2) frame is popped.
   • Control returns to factorial(3). It receives 2 and computes 3 * 2 = 6. The factorial(3) frame is popped.
   • Control returns to factorial(4). It receives 6 and computes 4 * 6 = 24. The factorial(4) frame is popped.
   • Finally, control returns to main(), with the final result of 24.

4. Hands-on: Making the Stack Visible

Just as we did with mergeSort, we can use printf statements to create a textual representation of the call stack's behavior. This is a powerful technique for visualizing and debugging recursive functions.

Your Task:
Compile and run the following C code. Observe the output and relate it directly to the push (winding) and pop (unwinding) phases we just discussed.

#include <stdio.h>

int factorial(int n) {
    printf("--> Calling factorial(%d). Pushing to stack.\n", n);
    
    // Base Case
    if (n == 0) {
        printf("<-- Base case n=0 reached. Returning 1. Popping from stack.\n");
        return 1;
    }
    // Recursive Step
    else {
        int recursive_result = factorial(n - 1);
        int my_result = n * recursive_result;
        printf("<-- Done with factorial(%d). Returning %d. Popping from stack.\n", n, my_result);
        return my_result;
    }
}

int main() {
    int number = 4;
    printf("Calculating factorial of %d\n", number);
    int result = factorial(number);
    printf("The factorial of %d is %d.\n", number, result);
    return 0;
}

When you run this code, you will see a series of "Calling..." messages as the stack builds up, followed by a series of "Done with..." messages as the stack unwinds. This output is a direct printout of the execution flow.

5. Why This Matters: Stack Overflow

What would happen if we forgot our base case, or if it was never reached?

int bad_factorial(int n) {
    // Missing or incorrect base case
    return n * bad_factorial(n - 1); 
}

If you call bad_factorial(4), it will call bad_factorial(3), then (2), (1), (0), (-1), (-2), and so on, forever. Each call pushes a new frame onto the stack. The stack, however, has a finite size. Eventually, it will run out of space, and the program will crash with a stack overflow error. This is one of the most common pitfalls in recursive programming, and understanding the call stack makes it obvious why it happens.

Conclusion

In this lesson, we demystified the process of recursion by examining the call stack. You have learned how this fundamental LIFO data structure manages every function call, enabling the elegant power of recursion.

Key Takeaways:

• The call stack is a LIFO structure used by C to manage function calls.
• Each function call creates a stack frame containing its parameters, local variables, and a return address.
• Recursion works by pushing multiple stack frames for the same function onto the stack.
• The base case stops the recursion and begins the "unwinding" process, where frames are popped off the stack and values are returned.
• A missing or unreachable base case leads to infinite recursion and a stack overflow error.

Preview of the Next Lesson:
We've used recursion to implement mergeSort and now understand how it works under the hood. The next logical step is to analyze its performance. In the next lesson, we will determine the time and space complexity of mergeSort, connecting its O(n log n) efficiency to the recursive division of the problem and the memory used by the call stack.