Tracing Recursive Functions: Base Case and Recursive Step

Hello! Last lesson, you connected node objects by following references. This lesson introduces a different way for a program to keep track of unfinished work: a function can call itself. You’ll learn to trace those calls, find the condition that stops them, and follow their return values back to the original call.

You already know how to use functions and conditionals. Recursion uses both; the new challenge is keeping track of which call is running and which calls are waiting. Allow about 30 minutes, including time to run the examples.

Find the stopping point first

A recursive function calls itself. Watch the two examples in Learn RECURSION in 5 minutes! by Bro Code. The countdown example establishes why a stopping condition matters; the factorial example shows a function that returns a value through several calls.

Here is a small countdown you can run:

def countdown(n):
    if n == 0:
        print("Done")
        return

    print(n)
    countdown(n - 1)

countdown(3)

It prints 3, 2, 1, then Done. The condition n == 0 is the base case: it handles an input without making another recursive call. The call countdown(n - 1) is the recursive step: it asks the same function to handle a smaller input.

These two parts must work together. For a nonnegative starting value, subtracting one eventually reaches zero. Without the base case—or if the argument did not move toward it—calls would continue until Python raised a RecursionError. This version assumes n starts nonnegative; starting at -1 would move away from zero.

Trace calls down and returns back up

Factorial makes the return path easier to see. For example, $3!=3\times 2\times 1=6$. Consider this function for positive integers:

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

print(factorial(3))  # 6

The base case is n == 1, where the answer is known immediately. The recursive step is factorial(n - 1), with the returned result multiplied by the current n.

When factorial(3) reaches return 3 * factorial(2), it cannot multiply yet: it needs the value of factorial(2). Each call has its own value of n and waits at its own multiplication:

Now follow the answers back up. factorial(2) receives 1 and returns 2 * 1, which is 2. Then factorial(3) receives 2 and returns 3 * 2, which is 6.

Python keeps the unfinished calls in call frames. Think of a frame as one call’s place in the function, including its own local n. The most recent call finishes first; earlier calls resume in reverse order. Unlike the node references in the previous lesson, you do not connect these frames yourself—Python manages them while the function runs.

Notice the function’s stated input assumption. With n == 0, this particular code would keep decreasing instead of reaching its base case. The familiar mathematical value $0!=1$ would require a different base-case condition.

Notice where work happens

A recursive call can sit between other statements. That changes the order in which you see results:

def announce(n):
    if n == 0:
        print("stop")
        return

    print("enter", n)
    announce(n - 1)
    print("leave", n)

announce(2)

The output is:

enter 2
enter 1
stop
leave 1
leave 2

enter prints before the next call. Each leave prints only after that next call has finished. At n == 0, the return ends that call without reaching either print below it.

For any small recursive trace, use this routine:

1. Mark the base case and its action or returned value.
2. Follow each recursive step, recording the argument for each new call.
3. At the base case, work backward through the waiting calls, completing any work after each recursive call.

That final pass matters. In countdown, there is no statement after the recursive call, so the returns are quiet. In factorial, multiplication happens as calls return. In announce, the leave lines print as calls return.

Key takeaways

A recursive function needs a base case that stops calling and a recursive step that moves valid inputs toward it. To trace one, follow the calls down, then follow the returns back up; each waiting call resumes with its own local values.

Next, you’ll use this tracing method to write a recursive function that processes a list.