Recursion Trace Tables: From Base Case to Return Value
Stack frames make recursion traceable once you tabulate calls and returns.
AA
Ameer Abdullah
Data Science Graduate · AI/ML & Data Science
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