Tracing Recursive Functions

Tracing recursive functions can be an effective technique for understanding their behavior and identifying bugs.

Using print statements

One common approach to tracing recursive functions is to use print statements to output the input arguments and intermediate results at each step of the recursion. For example, consider the following recursive function that calculates the factorial of a positive integer:

def factorial(n):
    if n == 0:
        result = 1
    else:
        sub_result = factorial(n - 1)
        result = n * sub_result
    return result

To trace this function using print statements, we can add statements to output the input argument and the intermediate result at each step of the recursion. We can also add an indent parameter, which we can use to change the level of indentation of the print statement to more clearly illustrate the nested recursive calls:

def factorial(n, indent):
    print(indent + f"factorial({n})")
    if n == 0:
        result = 1
    else:
        sub_result = factorial(n - 1, indent + '  ')
        result = n * sub_result
    print(indent + f"result = {result}")
    return result

Note that with each recursive call, the level of indentation is increased (indent + ' '). The level of indentation increases the length of the whitespace string to more clearly show which recursive calls are nested within each other.

This approach can be useful for small and simple functions, but may be cumbersome for complex recursion.

Try stepping through this code as factorial(5, '') executes ('' is the initial level of indentation):

Using diagrams

You may have noticed in the previous example in Python Tutor that the runtime stack changed as the recursion executed. It can indeed be helpful to visualize the stack as the recursion executes -- this can help us understand that each call to the recursive function has its own stack frame and state. It also illustrates that after the base case is reached, all of the recursive calls must be "returned through" in order for the recursive process to complete.

Watch the following video to see an example of tracing a recursive function with a stack diagram:

Tracing example

Below is another example of a recursive function, that counts up from a to b:

Try tracing the execution of count(1, 5). You should see the output as:

1
2
3
4
5

Now consider the following modification, which swaps the two lines in the else clause:

def count(a, b):
    if a >= b:
        print(a)
    else:
        # below statements are reversed
        count(a + 1, b)
        print(a)

What do you think will be the output of count(1, 5) with this modification? To figure it out, try drawing the runtime stack while tracing the execution of the code. Is anything different about the output? If needed, try putting the code into Python Tutor.