Recursive Algorithms & Recurrence Relations

Algorithms & Complexity

Chapter 5 · Recursive Algorithms & Recurrence Relations

Chapters 3–4 analyzed code that repeats through loops. Recursive code repeats by calling itself — and analyzing its complexity needs a genuinely different tool: a recurrence relation, an equation defining a function's cost in terms of its own cost at smaller inputs.

From Code to Recurrence

The general shape

T(n) = [number of recursive calls] × T([size of each subproblem]) + [non-recursive work per call], with a base case like T(0) = O(1) to anchor it.

Example 1: Linear Recursion

def countdown(n):
    if n <= 0:
        return
    print(n)
    countdown(n - 1)

One recursive call, on an input one smaller, plus O(1) work: T(n) = T(n−1) + c, T(0) = c.

Unrolling: T(n) = T(n−1)+c = T(n−2)+2c = ... = T(0)+nc = c + nc = c(n+1) — O(n). Verified directly: countdown(10) makes exactly 11 calls (n=10 down through n=0) — matching n+1.

Proving the Solution — Exactly Discrete Mathematics Fundamentals Chapter 8's Own Technique

Claim: T(n) = c(n+1) for all n ≥ 0. This is proven by induction — the same base-case-plus-inductive-step structure that course used to prove a recursive function correct, now applied to prove a recursive function's cost:

Step	Working
Base case	`T(0) = c(0+1) = c` — matches the definition exactly
Inductive hypothesis	Assume `T(k) = c(k+1)` for some `k ≥ 0`
Inductive step	`T(k+1) = T(k) + c = c(k+1) + c = c(k+2) = c((k+1)+1)` — matches the formula at `n=k+1`

Both steps hold, so T(n) = c(n+1) is proven for every n — not just checked on a few examples.

Example 2: Naive Fibonacci — Exponential Blowup

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Two recursive calls, each on a slightly smaller input, plus O(1) work: T(n) = T(n−1) + T(n−2) + c.

A quick, honest upper bound — not the tightest one

Since T(n−2) < T(n−1), replacing both terms with the larger one gives T(n) ≤ 2T(n−1) + c, which unrolls the same way as Example 1's pattern to O(2ⁿ). This is a valid, easily-derived upper bound — the actual tight bound is Θ(φⁿ) where φ ≈ 1.618 (the golden ratio), genuinely smaller than 2ⁿ but harder to derive by hand. O(2ⁿ) is honest and sufficient for this course's own scope; it just isn't the tightest possible statement.

Real call counts confirm the exponential shape, even below the loose 2ⁿ ceiling:

n	Actual calls	2ⁿ (upper bound)
10	177	1,024
15	1,973	32,768
20	21,891	1,048,576

Example 3: Divide-and-Conquer — A Forward Reference

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)  # O(n) to merge two sorted halves

T(n) = 2T(n/2) + O(n) — exactly Chapter 6's next subject

Two recursive calls, each on half the input, plus O(n) work to merge the results back together. This shape — a fixed number of calls on a fraction of the input, plus polynomial extra work — is the single most common recurrence pattern in real divide-and-conquer algorithms, and it's exactly what Chapter 6's Master Theorem exists to solve directly, without unrolling by hand.

Recurrences in Code

def countdown_call_count(n):
    if n <= 0:
        return 1
    return 1 + countdown_call_count(n - 1)

print(countdown_call_count(10))  # 11 — matches T(n) = c(n+1) with c=1

def fib_call_count(n):
    if n <= 1:
        return 1
    return 1 + fib_call_count(n - 1) + fib_call_count(n - 2)

print(fib_call_count(10))   # 177 — well under 2^10 = 1024, but still exponential

Hands-On Exercises

Exercise 1

A recursive power function computes xⁿ as x * power(x, n-1), with base case power(x, 0) = 1. Write its recurrence relation, then solve it by unrolling, following this chapter's own Example 1 method exactly.

📄 View solution

Exercise 2

A recursive function makes 3 recursive calls, each on a third (n/3) of the original input, plus O(n) work to combine the results. Write this function's recurrence relation, following the exact shape of this chapter's own merge sort example.

📄 View solution

Exercise 3

A recurrence is defined as T(n) = T(n−1) + 2, T(0) = 5. Using this chapter's own induction method, prove that T(n) = 2n + 5 for all n ≥ 0, showing the base case and the full inductive step.

📄 View solution

Chapter 5 Quick Reference

Recurrence relation: T(n) = [calls] × T([subproblem size]) + [non-recursive work], anchored by a base case
Linear recursion: T(n) = T(n−1) + c unrolls to O(n) — provable exactly by Discrete Mathematics Fundamentals Chapter 8's own induction technique
Naive double recursion (like Fibonacci): T(n) = T(n−1) + T(n−2) + c — a quick, honest upper bound is O(2ⁿ), though the tight bound Θ(φⁿ) is smaller
Divide-and-conquer: T(n) = 2T(n/2) + O(n) (merge sort's own shape) — Chapter 6's Master Theorem solves this pattern directly
Next chapter: Solving recurrences — substitution and the Master Theorem