04Module · Goodrich Ch. 4

Week 4 — Recursion

Linear, binary, and multiple recursion; analyzing recursive algorithms; designing recursive solutions and eliminating tail recursion.

Recursion

Factorial, ruler, binary search, file-system examples, recursion depth, and tail-call elimination.

Theory

A recursive method calls itself on a strictly smaller instance and terminates at a base case.

Recurrences like T(n) = a·T(n/b) + f(n) are solved by the Master Theorem, giving Θ bounds for divide-and-conquer.

Linear recursion makes one call (factorial); binary makes two (binary search trees, mergesort); multiple makes several (file-system walks).

Python caps recursion depth (default 1000) — convert deep tail-recursive code into a loop manually.

Key points

Every recursion needs a base case AND demonstrable progress toward it.
Binary search runs in O(log n); the recurrence is T(n) = T(n/2) + O(1).
Use memoization (functools.lru_cache) to collapse repeated subproblems from exponential to polynomial.

Code examples

Binary search (recursive)

def binary_search(data, target, lo, hi):
    if lo > hi:
        return False
    mid = (lo + hi) // 2
    if data[mid] == target:
        return True
    if target < data[mid]:
        return binary_search(data, target, lo, mid - 1)
    return binary_search(data, target, mid + 1, hi)

Memoized Fibonacci

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(50))  # instant — O(n) with cache