Recursive thinking in programming is closely related to mathematical induction. The following is a quote from "Thinking recursively with Java" by Eric Roberts where he compares induction and recursion. Recursive thinking has a parallel in mathematics which is called mathematical induction. In both techniques, one must (1) determine a set of simple cases for which the proof or calculation is easily handled and (2) find an appropriate rule which can be repeatedly applied until the complete solution is obtained. In recursive applications, this process begins with the complex cases, and the rule successively reduces the complexity of the problem until only simple cases are left. When using induction, we tend to think of this process in the opposite direction. We start by proving the simple cases, and then use the inductive rule to derive increasingly complex results.... There are several ways to visualize the process of induction. One which is particularly compelling is to liken the process of an inductive proof to a chain of dominos which are lined up so that when one is knocked over, each of the others will follow in sequence. In order to establish that the entire chain will fall under a given set of circumstances, two things are necessary. To start with, someone has to physically knock over the first domino. This corresponds to the base step of the inductive argument. In addition, we must also know that, whenever any domino falls over, l knock over the next domino in the chain. If we number the dominos, this requirement can be expressed by saying that whenever domino N falls, it must successfully upset domino N+1. This corresponds to using the inductive hypothesis to establish the result for the next value of N More formally, we can think of induction not as a single proof, but as an arbitrarily large sequence of proofs of a similar form. For the case N-1, the proof is given explicitly. For larger numbers, the inductive phase of the proof provides a mechanism to construct a complete proof for any larger value. For example, to prove that a particular formula is true for N = 5, we could, in principal, start with the explicit proof for N-1 and then proceed as follows Since s true for N -1, I can prove it for N 2. Since I know it is true for N-2, I can prove it for N-3 Since I know it is true for N = 3, I can prove it for N = 4 Since I know it is true for N-4, I can prove it for N-5 In practice, of course, we are not called upon to demon strate a complete proof for any value, since the inductive mechanism makes it clear that such a derivation would be possible, no matter how large a value of N is chosen Recursive algorithms proceed in a very similar way. Suppose that we have a problem based on a numerical value for which we know the answer when N = l. From there, all that we need is some mechanism for calculating the result for any value N in terms of the result for N- 1. Thus, to compute the solution when N -5, we simply invert the process of the inductive derivation To compute the value when N = 5, I need the value when N = 4 To compute the value when N = 4, I need the value when N = 3 To compute the value when N-3, I need the value when N-2. To compute the value when N-2, I need the value when N-1 I know the value when N = 1 and can use it to solve the rest The following example illustrates the relation between mathematical induction and recursive implementation. Consider the following summation: -1 21. We can prove by mathematical induction that -121 = n(n + 1) Base case: n-1. Then, 1_1 21-2-n (n + 1)
