Tracing Recursion: factorial(n)

Recursion creates multiple stack frames. We show a frame-by-frame trace and describe how memoization reduces repeated work.

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

print(factorial(4))  # expected 24

Frame trace

1. Frame1: factorial(4) calls factorial(3)
2. Frame2: factorial(3) calls factorial(2)
3. Frame3: factorial(2) calls factorial(1)
4. Frame4: factorial(1) returns 1; Frame3 returns 2; Frame2 returns 6; Frame1 returns 24

Memoization tip

from functools import lru_cache

@lru_cache(maxsize=None)
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n-1)

Memoization stores previously computed results and prevents repeated recursive work. For factorial, it isn't strictly necessary, but for Fibonacci-style trees it reduces O(2^n) to O(n).