Recursion & Dynamic Programming

Fibonacci Recursion & Call Stack Tracing

The Fibonacci sequence is the classic computer science problem used to teach recursive function calls, call stack depth, and the need for dynamic programming memoization.

Naive TimeO(2^N)

Memoized TimeO(N)

Naive SpaceO(N)

Memoized SpaceO(N)

Naive Recursion (Tree Expansion)

Shows stack frames multiplying at each branch.

Trace Call Stack

def fib(n):
    # Base cases: fib(0) = 0, fib(1) = 1
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    # Recursive calls expand the call stack
    return fib(n - 1) + fib(n - 2)

result = fib(5)
print(f"fib(5) = {result}")

Memoized Fibonacci (Linear Time)

Caches subproblems in a dictionary table.

Trace Call Stack

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

result = fib_memo(10)
print(f"fib(10) = {result}")