Teaching Recursion with Trace Tables Instead of Hand-Waving

Teaching Recursion with Trace Tables Instead of Hand-Waving

Recursion feels abstract until learners can see stack movement. Trace tables make each call visible and reduce confusion quickly.

Step 1: Start with a small deterministic function

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

Step 2: Record call depth and return values

depth | call         | returns
0     | factorial(4) | 24
1     | factorial(3) | 6
2     | factorial(2) | 2
3     | factorial(1) | 1

Step 3: Convert the same logic to iterative form

def factorial_iter(n):
    out = 1
    for i in range(2, n + 1):
        out *= i
    return out

Pitfalls

• Introducing tree recursion before base-case mastery.
• Skipping stack visualization in teaching materials.
• No comparison with iterative equivalent.

Validation

• Learners can explain base case and recursive step clearly.
• Trace table answers match code execution.
• Students can rewrite recursion as loops.