Thinking Recursively with Java

2.1. Mathematical Induction

Recursive thinking has a parallel in mathematics that is called mathematical induction. With both techniques, one must (1) determine a set of simple cases for which the calculation or proof is straightforward, and (2) find an appropriate rule that you can apply repeatedly until you have obtained a complete solution. In recursive applications, this process begins with the complex cases, and the rule successively reduces the complexity of the problem until only simple cases remain. Induction works in the opposite direction. You start by proving the simple cases, and then use the inductive rule to derive increasingly complex results.

The nature of an inductive proof is most easily explained in the context of an example. In many mathematical and computer science applications, you need to compute the sum of the integers from 1 up to some maximum value N. You could certainly calculate this number by taking each number in order and adding it to a running total. Unfortunately, calculating the sum of the integers from 1 to 1000 by this method would require 999 additions, which you would quickly tire of performing in longhand. A much easier approach involves using the mathematical formula

While this formula is certainly more convenient, it will seem appropriate only if you can be convinced of its correctness.

For many formulae of this sort, mathematical induction ...