Lesson · Induction and Recursion · Recursion

Recursive Algorithms and Correctness

A recursive algorithm mirrors a recursive definition, and its correctness proof mirrors an induction. Two obligations: it terminates, and it returns the right answer when it does.

Open the interactive lesson Practice

TERMINATION every call reduces a quantity bounded below CORRECTNESS base case right, and recursive case right GIVEN the calls are Both are needed. Either alone is worthless. The proof is strong induction on the size of the input.

Two separate obligations

Core ideas

What this lesson establishes

Correctness of a recursive algorithm splits cleanly in two, and the split is what makes the proofs short.

Termination is a separate proof

Find a quantity that strictly decreases at every call and cannot decrease forever. Usually the input size; sometimes something less obvious.

Correctness assumes the recursive calls work

That is the inductive hypothesis. You do not trace the recursion; you assume smaller inputs are handled and check the combination.

A correct algorithm that never stops is not correct

And a terminating one that returns nonsense is not either. The two obligations are independent.

The material

Recursive algorithms

Three algorithms, each with both obligations discharged.

Factorial

FACTORIAL(n): if n = 0: return 1 else: return n × FACTORIAL(n − 1)

Termination. Each call has argument one smaller, and the argument is a natural number, so it cannot decrease past 0. The sequence of calls is finite.

Correctness. By induction on n. At n = 0 the algorithm returns 1, which is 0!. For n ≥ 1, assume the call FACTORIAL(n−1) returns (n−1)!; the algorithm returns n · (n−1)! = n! by the recursive definition of factorial.

Binary search

SEARCH(A, lo, hi, x): # A sorted ascending if lo > hi: return NOT FOUND mid = ⌊(lo + hi)/2⌋ if A[mid] = x: return mid if A[mid] < x: return SEARCH(A, mid + 1, hi, x) else: return SEARCH(A, lo, mid − 1, x)

Termination. The quantity hi − lo + 1 — the size of the range — strictly decreases at every recursive call, because mid is inside the range and is excluded from both subproblems. It is bounded below by 0, at which point the first line returns.

Correctness. By strong induction on the range size. If the range is empty, x is not in it and NOT FOUND is right. Otherwise, if A[mid] = x the index is right. If A[mid] < x then, because A is sorted, every index at or below mid holds a value less than x, so x can only be in the upper half; the hypothesis says the recursive call handles that smaller range correctly. The other branch is symmetric.

The sortedness assumption is doing the real work: it is what licenses discarding half the array. Applied to unsorted data the algorithm still terminates and returns confident wrong answers, which is the most dangerous kind of failure.

Merge sort

MERGESORT(A): if |A| ≤ 1: return A split A into halves L and R return MERGE( MERGESORT(L), MERGESORT(R) )

Termination. Each call receives an array of size at most ⌈n/2⌉ < n for n ≥ 2, and size is a natural number.

Correctness. Strong induction on |A|. Arrays of size 0 or 1 are already sorted. Otherwise the hypothesis says both recursive calls return sorted arrays, and MERGE of two sorted arrays is sorted — which is itself a small proof, by induction on the number of elements merged.

Notice the shape. Nothing traced the recursion; the argument assumed the subcalls worked and checked the combining step. That is why recursive correctness proofs are short while tracing recursive execution by hand is not.

Theorem · The two obligations are independent

An algorithm can terminate and be wrong (binary search on unsorted data), and can be "correct if it terminates" and never terminate (a recursion that fails to decrease). Both proofs are required.

Interactive

Algorithms and growth

Counts from running, not from quoting

Binary search, counted

The comparison counts are produced by running both searches. The binary column matches ⌊log₂n⌋ + 1 exactly, which is the termination argument turned into a bound: at n = 32 the counted worst cases are 32 and 6. The array the lab searches is sorted, which is what the correctness half of the proof needs and the termination half does not — on unsorted data the count would be the same and the answer wrong, which is the third quiz question.

What to examine

f(n)

g(n)

Input order

Growth policy

a (subproblems)

b (shrink factor)

d (combining cost n^d)

n16

measured—

predicted—

Method

Proving a recursive algorithm correct

Termination first, then correctness assuming the calls.

Find the decreasing quantity

Input size, range width, remaining depth. It must strictly decrease at every recursive call and be bounded below.

Check the base case handles the smallest inputs

And check that the recursion actually reaches it. A base case for n = 0 with a recursion that skips from 2 to 0 needs care about odd inputs.

Assume the recursive calls are correct

This is the strong inductive hypothesis. Do not trace — assume.

Verify the combining step

Given correct answers on the subproblems, does the algorithm produce the right answer for the whole? That is where the real content is.

Recursive correctness

Score 0 / 0

Choose the answer you can justify.

Fast exponentiation

Computing aⁿ in about log₂ n multiplications rather than n.

POWER(a, n): if n = 0: return 1 if n is even: h = POWER(a, n/2); return h × h else: return a × POWER(a, n − 1) TERMINATION n decreases at every call (halved, or reduced by 1) and is bounded below by 0. CORRECTNESS strong induction on n. n = 0: returns 1 = a⁰. ✓ n even: hypothesis gives h = a^(n/2); h × h = a^(n/2) · a^(n/2) = aⁿ. ✓ n odd: hypothesis gives a^(n−1); a × a^(n−1) = aⁿ. ✓ Cost: at most 2·log₂ n calls — two odd steps never occur in a row.

Strong induction is essential here: the even branch reaches back to n/2, not to n − 1. Ordinary induction would give a hypothesis about the wrong value. “Modular Exponentiation” in Number Theory and Cryptography uses this algorithm as modular exponentiation, where the saving is the difference between feasible and impossible.

Common mistakes

Proving correctness and forgetting termination"Correct if it terminates" is worth nothing for an algorithm that does not. The two obligations are separate and both are required.

Tracing instead of assumingFollowing the recursion by hand does not generalise past the input you traced. The hypothesis covers all smaller inputs at once.

Overlooking a preconditionBinary search needs sorted input; merge needs sorted halves. A precondition used but not stated is a proof of a different theorem.

Check your understanding

✓

Finish when you can discharge both obligations in a paragraph.

Write a recursive algorithm computing the nth Fibonacci number, prove it terminates and prove it correct. Then count the calls it makes: the naive version makes exponentially many — about φⁿ, the root “Solving Linear Recurrences” finds for this recurrence — and “Dynamic Programming” in Algorithms and Complexity returns to fix that.

Note: The naive recursive Fibonacci makes about 1.6ⁿ calls because it recomputes the same subproblems repeatedly. Storing results — memoisation — drops it to n calls, and that observation is the whole idea of dynamic programming in “Dynamic Programming” in Algorithms and Complexity.