Prev: The Basis Cases
Next: Loop Invariants
- by Brad Bart, Simon Fraser University
- Programming Using Induction
- Loop Invariants
- Invariants and Recursive Algorithms
Induction is about mathematical structures which are self-similar. So are algorithms and computer programming, both of which apply recursion and iteration to solve problems.
Induction and Recursion
Recursion is an algorithmic technique where you solve a problem by using the solutions to smaller instances of the same problem.
The inductive step from the squares example was recursive because in order to verify the nth case, you relied on the n − 1st case. But similarly, case n − 1 depended on case n − 2. And case n − 2 depended on case n − 3, which depended on case n − 4, . . ., which depended on case 3, which depended on case 2, which depended on case 1. And since case 1 was verified in the basis step, you concluded the nth case was true.
This sort of recursive reasoning, where you break down the large case
into smaller cases, is known as the top-down approach.
In this example, it leads directly to a recursive implementation of the
function SumOdd(n), which for positive n returns the
sum of the first n odd integers: the resulting sum
is based on a call to SumOdd(n-1), when n > 1.
The case for n = 1,
where the recursion stops, is the
base case.
int SumOdd(int n) {
// base case
if (n == 1) return 1;
// recursive case
return SumOdd(n-1) + (2*n - 1);
}
Induction and Iteration
The other way to look at induction is by starting with case 1, the basis case. Then, by using the inductive step, case 1 implies case 2. Now that you have case 2, you use the inductive step again, and you have case 3. Case 3 implies case 4, which implies case 5, which implies case 6, and so on, climbing your infinite ladder, rung by rung, going as high as you like.
This sort of recursive reasoning, where you use the smaller cases to
build up to the large case, is known as the bottom-up approach.
In the squares example, it leads directly to an iterative implementation
of the function SumOdd(n), defined as before. This time a
variable total holds the running
sum of the first i-1 odd integers.
In each iteration, the ith
odd integer
is added to the running sum.
int SumOdd(int n) {
total = 1;
for (int i = 2; i <= n; ++i) {
// assert(total == (i-1)*(i-1));
total += (2*i - 1);
// assert(total == i*i);
}
}
The two assertions in the implementation serve to convince the
reader that the code does just what it is supposed to do: that at
the beginning of the loop
∑ = (i − 1)2, and at the end of
the loop
∑ = i2.
An assertion about how the data of the
algorithm relate to the loop index is called a loop invariant.
Next: Loop Invariants