Recursive Functions: from $n!$ to $\mathrm{Fib}(n)$

From frames to self-calls

• Recap: frames = name $\to$ value bindings
• New move: a procedure refers to itself (recursion)
• Question: after we trace factorial, what are the process shape and its cost ($\Theta$ time, $\Theta$ space)?

A definition can compute

$$ n! = \begin{cases}1 & n=0\ \,(n-1)! & n>0 \end{cases} $$

• Two parts: base case $+$ smaller subproblem
• Key question: what process does this definition generate?

Factorial in Python: linear recursion

def fact(n):
    """Return n! for n >= 0."""
    if n == 0:
        return 1
    return n * fact(n - 1)

# quick sanity checks
print(fact(0))  # 1
print(fact(5))  # 120

• Base case: $n=0$
• Recursive case: shrink $n \mapsto n-1$

Tracing $\mathrm{fact}(4)$: expansion then contraction

def fact_debug(n):
    print("enter", n)
    if n == 0:
        print("base")
        return 1
    result = n * fact_debug(n - 1)
    print("exit", n, "->", result)
    return result
fact_debug(4)

• Call stack: frames build up, then unwind
• Checkpoint: order of the "enter" prints for input $4$

Tree recursion: Fibonacci as the cautionary tale

def fib(n):
    """Return Fib(n) for n >= 0 (naive tree recursion)."""
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)
print(fib(6))  # 8

• Linear recursion: $1$ self-call per call (like $n!$)
• Tree recursion: $2$ self-calls per call (like $\mathrm{Fib}(n)$)

The $\mathrm{fib}(5)$ call tree and exponential time

• fib(5) expands into many repeated subcalls
• Call-tree start: fib(5) → fib(4) + fib(3), and fib(4) → fib(3) + fib(2)
• Let T(n) be the number of calls: T(n) = T(n-1) + T(n-2) + O(1)
• So T(n) grows like Fibonacci numbers, giving time $\Theta(\varphi^n)$ and space $\Theta(n)$
• Checkpoint: In the full call tree for fib(6), how many times is the base case reached (calls with n <= 1)? (Expected: 21; fib(0) occurs 8 times and fib(1) occurs 13 times)

Memoization: same recursion, no repeats

def fib_memo(n, memo=None):
    """Return Fib(n) using recursion + memoization."""
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]
print(fib_memo(30))  # fast

• Cache: dictionary of computed values $k \mapsto \mathrm{Fib}(k)$
• Growth: time $\Theta(n)$, space $\Theta(n)$

Iteration as a process: carry state explicitly

def fib_iter(n):
    """Return Fib(n) in O(n) time and O(1) extra space."""
    a, b = 1, 0  # a = Fib(1), b = Fib(0)
    count = n
    while count != 0:
        a, b = a + b, a
        count -= 1
    return b
print(fib_iter(6))  # 8

• Invariant: after k updates, (a, b) $=$ ($Fib(k+1$), Fib(k))
• Each step updates the whole state with (a, b) ← (a $+$ b, a)

Counting change: recursion for real decomposition

def count_change(amount, coins=(50, 25, 10, 5, 1)):
    """Number of ways to make 'amount' using the given coin denominations."""
    coins = tuple(coins)

    def cc(a, i):
        # a = remaining amount, i = index into coins
        if a == 0:
            return 1
        if a < 0 or i == len(coins):
            return 0
        # skip coin i OR use coin i
        return cc(a, i + 1) + cc(a - coins[i], i)

    return cc(amount, 0)
print(count_change(10, coins=(10, 5, 1)))  # 4

• Split rule: skip a coin vs use a coin
• Base cases: $a=0$ gives $1$; $a<0$ or no coins gives $0$

Exit ticket: predict, then explain

• Practice: ways to make $10$ with coins $\{1,5,10\}$
• Reflection: when should you prefer memoization vs an iterative process?