DEV Community

Cover image for How to Read a Recursive Function Without Losing Your Mind
Ameer Abdullah
Ameer Abdullah

Posted on

How to Read a Recursive Function Without Losing Your Mind

#python #tutorial #codenewbie #beginners

Recursion is not difficult. Tracing recursion is difficult.

The reason is that most people try to hold the entire call stack in their head simultaneously. You cannot do this reliably for more than three or four levels. Your working memory runs out and you lose track.

The solution is a systematic method that keeps information on paper instead of in your head. Once you have this method, you can trace any recursive function regardless of depth.

The Two-Column Method

Draw two columns on paper before you trace a single line.

Left column: the function call and its argument.
Right column: what it returns.

You fill in the left column going down. You fill in the right column coming back up.

Applying It to a Simple Example 

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

print(factorial(4))
Enter fullscreen mode Exit fullscreen mode

Fill in the left column first, going down until you hit the base case:

factorial(4)    |  ?
factorial(3)    |  ?
factorial(2)    |  ?
factorial(1)    |  ?
factorial(0)    |  1   <-- base case, fill right column here
Enter fullscreen mode Exit fullscreen mode

Now fill the right column coming back up. Each row gets the return value of the row below it:

factorial(4)    |  24   (4 * 6)
factorial(3)    |  6    (3 * 2)
factorial(2)    |  2    (2 * 1)
factorial(1)    |  1    (1 * 1)
factorial(0)    |  1
Enter fullscreen mode Exit fullscreen mode

The answer is 24.

The Method on a Harder Example 

def mystery(n):
    if n <= 0:
        return 0
    if n % 2 == 0:
        return mystery(n - 2) + n
    return mystery(n - 1)

print(mystery(6))
Enter fullscreen mode Exit fullscreen mode

Left column going down:

mystery(6)    n=6, even, so mystery(4) + 6
mystery(4)    n=4, even, so mystery(2) + 4
mystery(2)    n=2, even, so mystery(0) + 2
mystery(0)    n<=0, return 0
Enter fullscreen mode Exit fullscreen mode

Right column coming back up:

mystery(6)    = mystery(4) + 6 = 6 + 6 = 12
mystery(4)    = mystery(2) + 4 = 2 + 4 = 6
mystery(2)    = mystery(0) + 2 = 0 + 2 = 2
mystery(0)    = 0
Enter fullscreen mode Exit fullscreen mode

Output: 12

The method works because it separates the two phases: descending (making calls) and ascending (returning values). You never have to hold both in mind simultaneously.

The Three Rules That Cover Every Recursive Problem

Rule 1: Always find the base case first. Write it in your right column before anything else. The base case is the only row you can fill in without looking at another row.

Rule 2: Fill the left column completely before touching the right column. Do not alternate. Write every call going down, then turn around and return values going up.

Rule 3: Each right column value is always computed using the values of the rows below it, never the rows above. If you find yourself looking upward in the right column to compute a value, you are doing it wrong.

These three rules prevent every category of recursion tracing error.

The Interview Version

Interviewers sometimes add a twist: asking what prints during the recursion, not just what returns.

def trace_me(n):
    if n == 0:
        print("base")
        return
    print(f"going down: {n}")
    trace_me(n - 1)
    print(f"coming up: {n}")

trace_me(3)
Enter fullscreen mode Exit fullscreen mode

Output:

going down: 3
going down: 2
going down: 1
base
coming up: 1
coming up: 2
coming up: 3
Enter fullscreen mode Exit fullscreen mode

The print before the recursive call fires on the way down. The print after the recursive call fires on the way back up. This pattern appears in tree traversal and many real-world algorithms.

Practice recursive tracing problems at PyCodeIt. The hard difficulty section includes several recursion problems that test exactly this ascending and descending behavior.

Top comments (0)