PyCodeItPython trace & interview prep
python

Recursion Trace Tables: Step-by-Step Guide

Stack frames make recursion traceable once you tabulate calls and returns.

AA

Ameer Abdullah

Data Science & AI/ML Graduate-GitHub-Dev.to

6 min read

Concept in Simple Words: Recursion is a function calling itself. Each recursive call creates a new stack frame in memory to hold local variables. To trace recursion, your table must have a column representing the stack depth. Do not mix variables from different recursive frames.

Deep Walkthrough & Code: Let's trace a recursive fibonacci function with a trace table:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)
Step-by-Step Dry Run: Let's trace fib(3). Our table columns are [Frame Depth, Active Call, Value of n, Returns].
- Frame 1: fib(3). n=3. n > 1, calls fib(2) + fib(1).
- Frame 2: fib(2). n=2. n > 1, calls fib(1) + fib(0).
- Frame 3: fib(1). n=1. Base case met. Returns 1 to caller (Frame 2).
- Frame 4: fib(0). n=0. Base case met. Returns 0 to caller (Frame 2).
- Frame 2: receives 1 and 0, returns 1 to caller (Frame 1).
- Frame 5: fib(1). n=1. Base case met. Returns 1 to caller (Frame 1).
- Frame 1: receives 1 (from fib(2)) and 1 (from fib(1)), returns 2.
Production Level Issue & Fix: The recursive Fibonacci function runs in O(2^n) time complexity and causes a StackOverflowError for large n. The production fix is to use memoization (cache intermediate results) or write it iteratively: `@functools.lru_cache(maxsize=None)
def fib(n):
    ...`.

Practice what you just learned

Apply these concepts in PyCodeIt's interactive sandbox with real problems.

Start Python Practice

Related Python Tutorials