Thinking Recursively with Java

Chapter 2. Mathematical Preliminaries

One cannot escape the feeling that these mathematical formulae have an independent existence and an intelligence of their own, that they are wiser than we are, wiser even than their discoverers.

—Heinrich Hertz

Many students who have become interested in computer science through their experience with programming respond with a certain level of distrust or disapproval to the idea that computer science requires a strong mathematical foundation. For those students, mathematics and programming often seem to represent antithetical aspects of the science of computing; programming is, after all, usually fun, and mathematics is, to many, quite the opposite.

In many cases, however, understanding the mathematical foundations of computer science can provide practical insights that dramatically affect the programming process. Recursive programming is an important case in point. As discussed in Chapter 1, programmers often find the concept of recursion difficult primarily because they lack faith in its correctness. In the attempt to gain this faith, experience is a critically important factor. For this reason, much of the book consists of programming examples and related exercises that reinforce the skills and tactics required for recursive programming. Another important factor that can increase one's level of confidence in recursion is the ability to prove, through cogent mathematical argument, that a particular recursive algorithm does what it is supposed ...