Recursive algorithms replace loop structure with self-reference. Instead of tracking progress through iteration, you track progress through problem size. A recursion invariant describes what each call is responsible for computing and how that responsibility relates to smaller subproblems.
The core idea is simple: every recursive call must solve a strictly smaller instance of the same problem, and the combination of those solutions must produce a correct result for the original input.
Problem
You have a recursive algorithm that appears to work, but you need a structured way to argue correctness and ensure that recursion terminates.
Solution
Use this structure:
1. Define the problem for input size n.
2. Specify the base case.
3. Assume correctness for smaller inputs (inductive hypothesis).
4. Show the recursive step produces a correct result using smaller solutions.
5. Show that recursion terminates.This mirrors mathematical induction. The recursion invariant is the statement that every call correctly solves its subproblem.
Example: Sum of Array
sum(A, n):
if n == 0:
return 0
else:
return sum(A, n - 1) + A[n - 1]Invariant:
sum(A, k) returns the sum of A[0..k-1] for every k ≤ n.Base case:
For k = 0, the function returns 0, which matches the sum of an empty prefix.
Inductive step:
Assume sum(A, k-1) correctly returns the sum of A[0..k-2]. Then:
sum(A, k) = sum(A, k-1) + A[k-1]which equals the sum of A[0..k-1].
Termination:
Each call reduces n by 1, so the recursion eventually reaches 0.
Example: Binary Search
binary_search(A, left, right, x):
if left > right:
return false
mid = (left + right) // 2
if A[mid] == x:
return true
else if A[mid] < x:
return binary_search(A, mid + 1, right, x)
else:
return binary_search(A, left, mid - 1, x)Invariant:
If x exists in A, then it exists within A[left..right].Base case:
If left > right, the interval is empty, so x does not exist.
Inductive step:
Each recursive call reduces the interval while preserving the invariant. If A[mid] < x, then all indices ≤ mid cannot contain x, so the search continues in [mid+1, right]. The symmetric case holds when A[mid] > x.
Termination:
The interval size decreases each step, so eventually left > right.
Designing Recursion Invariants
A recursion invariant should describe what the function returns for any valid input. It should not depend on how the function is called. This makes the argument compositional.
Common patterns include:
Divide and combine
Solve subproblems independently and combine results.Reduce and extend
Solve a smaller instance, then extend to the full problem.Search and prune
Restrict the search space and recurse on valid regions.Base Cases
Base cases must satisfy two conditions:
- They are correct by direct reasoning
- They stop further recursion
Incorrect base cases are a common source of errors. If the base case does not match the problem definition exactly, the entire recursion becomes invalid.
Termination
Termination requires a measure that decreases with each recursive call. Typical measures include:
- Size of input
- Length of interval
- Depth of structure (tree height)
The measure must be non-negative and strictly decrease in every recursive branch.
Common Pitfalls
A recursive definition that does not reduce the problem size leads to infinite recursion.
A recursion invariant that depends on external state breaks composability. Each call should be correct independently.
Combining results incorrectly often passes simple tests but fails in edge cases. The combination step must be justified explicitly.
Ignoring overlapping subproblems leads to inefficient recursion. This is addressed later with dynamic programming.
Takeaway
A recursion invariant states that each call correctly solves its subproblem. Correctness follows from base cases, inductive reasoning, and proper combination of results. Termination follows from a decreasing measure.