How it works
A recursive method is argued correct by assuming the recursive call works on a smaller input and showing the combination step is right.
Write the argument in two parts: base case correct, and recursive step correct given the assumption.
Common error
Tracing one example and calling it a proof. A trace is evidence, not an argument.
Worked example
Java snippets run inside a main method. Add import java.util.*; when collection types are used.
Java
class Solver {
int count(int[] a, int i) {
if (i == a.length) return 0;
return (a[i] > 0 ? 1 : 0) + count(a, i + 1);
}
}
System.out.println(new Solver().count(new int[]{-1, 3, 4}, 0));Output
2The recursive claim is that count(a, i) counts positives in the suffix starting at i. The empty suffix has count zero. The step adds the current contribution to a correctly counted shorter suffix.
Exercises
1.3.1 · Explain
State a decreasing measure for count(a, i).
Show solution
The number of unprocessed elements, a.length - i, decreases by one on each recursive call until it is zero.
1.3.2 · Explain
Why is checking the base case alone not a full correctness argument?
Show solution
It covers only the smallest input. Also show the recursive subproblem is smaller and that combining its correct result produces the required result for the current input.