Generating Recursion Trees (Trace Shapes)

Generating recursion trees as artifacts helps teach: emit Graphviz or ASCII for small parameters to show overlapping subproblems.

Why this shows up in the real world

Education tools auto-layout recursion traces; debuggers show call stack frames.

Core idea (explained for students)

Instrument recursion with depth parameter indent printing—only for tiny n in contests.

Try this in Python

def trace(n: int, indent: int = 0) -> int:
    print('  ' * indent + f'fib({n})')
    if n <= 1:
        return n
    return trace(n - 1, indent + 1) + trace(n - 2, indent + 1)


trace(4)

Common mistakes

• IO heavy tracing in timed contests—disable in submit.
• Logging sensitive data in production.

Key takeaways

• Use decorators @trace for local dev only.
• Pair traces with memoization to see collapse to DAG.