Ameer Abdullah

Posted on Jun 26

5 Python Recursion Problems That Will Make You Finally Understand Base Cases

#python #programming #tutorial #beginners

Recursion feels abstract until you trace it. Once you trace it, it becomes obvious.

Here are five problems in order of difficulty. For each one, trace it before reading the answer.

Problem 1 — Countdown

def countdown(n):
    if n <= 0:
        print("done")
        return
    print(n)
    countdown(n - 1)

countdown(3)

Trace it. What prints?

Output:

3
2
1
done

Note that print(n) happens before the recursive call. The current value prints, then the function calls itself with a smaller value.

Problem 2 — Count Up

def countup(n):
    if n <= 0:
        return
    countup(n - 1)
    print(n)

countup(3)

This looks almost identical to Problem 1 but the output is the reverse. What prints?

Output:

1
2
3

The recursive call happens before print(n). The function goes all the way down to the base case first, then prints on the way back up. This is the key difference between head recursion and tail recursion.

Problem 3 — Sum of Digits

def digit_sum(n):
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)

print(digit_sum(1234))

Trace the call stack:

digit_sum(1234): 4 + digit_sum(123)
digit_sum(123): 3 + digit_sum(12)
digit_sum(12): 2 + digit_sum(1)
digit_sum(1): returns 1 (base case, n < 10)

Adding back up: 2 + 1 = 3, then 3 + 3 = 6, then 6 + 4 = 10

Output: 10

Problem 4 — The Tricky Return

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

print(mystery(5))

Trace:

mystery(5): 5 is odd, so 5 + mystery(4)
mystery(4): 4 is even, so mystery(3)
mystery(3): 3 is odd, so 3 + mystery(2)
mystery(2): 2 is even, so mystery(1)
mystery(1): 1 is odd, so 1 + mystery(0)
mystery(0): returns 0

Building back: 1 + 0 = 1, mystery(1) = 1, mystery(2) = 1, 3 + 1 = 4, mystery(3) = 4, mystery(4) = 4, 5 + 4 = 9

Output: 9

Problem 5 — Multiple Return Paths

def count_evens(lst):
    if not lst:
        return 0
    return (1 if lst[0] % 2 == 0 else 0) + count_evens(lst[1:])

print(count_evens([1, 2, 3, 4, 5, 6]))

Each call checks the first element and adds 1 if even, then recurses on the rest.

Elements: 1 (odd, 0), 2 (even, 1), 3 (odd, 0), 4 (even, 1), 5 (odd, 0), 6 (even, 1), then empty list returns 0.

Sum: 0 + 1 + 0 + 1 + 0 + 1 + 0 = 3

Output: 3

For more recursion problems with AI-generated variations and trace explanations, try PyCodeIt. Free, unlimited, unique every session.

DEV Community