Metadata Card

• Prerequisites: Chapter 3 — Proof Methods (induction)
• Estimated time: 45 minutes
• Core difficulty: Intermediate
• Completion marker: Able to write mathematical definitions of recursive functions, distinguish recurrence from recursion, and solve simple recurrence relations

Your Progress

The first three floors taught you logic, sets, and proofs. The stone door on the fourth floor is made of mirrors — look inside, and a painting on the wall contains another painting of the same scene.

Your Task

You've written a recursive function — it calls itself. But why does it terminate? How do you analyze its time complexity? "Recursion" is often taught as a "programming technique," but its mathematical roots are thousands of years older than programming. This chapter lets you understand the mathematical essence of recursion — recurrence relations and their solution methods.

Chapter Layers

• Required reading: Recursive definitions, recurrence relations, master theorem
• Optional reading: Generating functions

Breakthrough · Origin Story

You implemented a binary search and wrote a Fibonacci function. Tests pass. But the interviewer asks: "What's the time complexity?" You start reciting formulas: T(n) = T(n/2) + O(1) is O(log n), T(n) = T(n-1) + T(n-2) is O(2ⁿ). Where do these formulas come from? Why do they work?

Recursive definition: Defining something in terms of itself. Three elements:

1. Base case: The simplest instance, giving a result directly.
2. Recursive rule: How to construct the current instance from smaller instances.
3. Termination: Each recursive call must reduce the problem size, eventually reaching a base case.

A mathematical recursive definition, such as the Fibonacci sequence:

You've written a naive recursive Fibonacci in code: return fib(n-1) + fib(n-2). The mathematical definition looks just like your code — but be careful: a concise definition doesn't mean efficient execution. Exponential complexity comes from massive redundant computation, which is exactly what memoization solves.

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)  (n ≥ 2)

A recurrence relation is the mathematical description of the time/space complexity of a recursive algorithm. The recurrence for binary search:

Binary search is the ideal specimen for analyzing recursive complexity. Each call halves the array and does a constant number of comparisons — this isn't estimated by intuition, but by a precise recurrence.

T(1) = 1
T(n) = T(n/2) + 1   (each call halves the problem size, plus one comparison)

Solving this recurrence by substitution:

The method of repeated substitution is like manually unwinding the call stack while debugging a recursive function. Starting from T(n), replace layer by layer until you hit T(1), and the complexity formula emerges during the unwinding.

T(n) = T(n/2) + 1
     = (T(n/4) + 1) + 1 = T(n/4) + 2
     = (T(n/8) + 1) + 2 = T(n/8) + 3
     = ...
     = T(1) + log₂(n)
     = 1 + log₂(n)
     = O(log n)

More generally, for recurrences of the form T(n) = aT(n/b) + f(n) (divide-and-conquer algorithms), there is the master theorem:

Given T(n) = aT(n/b) + f(n), where a ≥ 1, b > 1:

• If f(n) = O(n^{log_b(a) - ε}), then T(n) = Θ(n^{log_b(a)})
• If f(n) = Θ(n^{log_b(a)}), then T(n) = Θ(n^{log_b(a)} log n)
• If f(n) = Ω(n^{log_b(a) + ε}), and the regularity condition a f(n/b) ≤ c f(n) holds, then T(n) = Θ(f(n))

Don't be intimidated by the notation. Practical usage scenarios:

• Binary search: a=1, b=2, f(n)=1. log_b(a)=log₂(1)=0, f(n)=Θ(1)=Θ(n⁰) → case 2, T(n)=Θ(log n)
• Merge sort: a=2, b=2, f(n)=n. log_b(a)=1, f(n)=Θ(n¹) → case 2, T(n)=Θ(n log n)
• Naive Fibonacci (recursive): a=2, b=1 doesn't apply — this isn't divide-and-conquer, it's linear recursion.

The relationship between recursion and iteration is worth noting. Any recursive algorithm can be converted to an equivalent iterative version (using an explicit stack). The reverse is not necessarily true — not all iterations can be naturally expressed as recursion. Recursion emphasizes "what it is" (declarative), while iteration emphasizes "how to do it" (procedural).

The recursive implementation (exponential time) and the iterative implementation (linear time) of Fibonacci are different computational paths for the same mathematical definition. Mathematics defines "what it is"; algorithms determine "how to compute it."

Common Pitfalls

• Forgetting the base case. Recursion without a base case is an infinite loop.
• Thinking recursion is always slower than iteration. Recursion's strength is in expressiveness — tree traversal, graph search, backtracking, etc., are often easier to get right with recursion than with iteration.
• Applying the master theorem to recurrences that don't fit the divide-and-conquer pattern. For example, T(n) = T(n-1) + n is not of the form aT(n/b) + f(n) and requires substitution or recursion tree methods.

Challenge Questions

• Write a recursive definition of n! (factorial), and use substitution to solve the recurrence T(n) = T(n-1) + 1 for its time complexity.
• Write the recurrence for merge sort and solve it using the master theorem.
• Implement three versions of the Fibonacci sequence: naive recursive, memoized recursive, and iterative. Compare their time complexities.

Traveler's Notes

Recursion is the intersection of mathematics and programming. Recurrence relations tell you "how fast"; recursive definitions tell you "what it is." The master theorem is a shortcut for solving divide-and-conquer recurrences.

→ Next stop: Recursion helps you handle self-reference within a single problem. But to describe "relationships between two things" or "a mapping from input to output," you need relations and functions.