Thinking Recursively with Java

Chapter 1. The Idea of Recursion

Of all ideas I have introduced to children, recursion stands out as the one idea that is particularly able to evoke an excited response.

—Seymour Papert, Mindstorms

At its essence, computer science is the study of problems and their solutions. More specifically, computer science is concerned with finding systematic procedures that guarantee a correct solution to a given problem. Such procedures are called algorithms.

This book is about a particular class of algorithms, called recursive algorithms, that turn out to be quite important in computer science. The use of recursion makes it possible to solve complex problems using programs that are surprisingly concise, easily understood, and algorithmically efficient. For the student seeing this material for the first time, however, recursion appears to be obscure, difficult, and mystical. Unlike problem-solving techniques that have closely related counterparts in everyday life, recursion is an unfamiliar idea and often requires thinking about problems in a new way. This book is designed to provide the conceptual tools necessary to approach problems from this recursive point of view.

Informally, recursion is the process of solving a large problem by reducing it to one or more subproblems that are (1) identical in structure to the original problem and (2) somewhat simpler to solve. Once you have made that original subdivision, you use the same decompositional technique to divide each of these subproblems ...