Thinking Recursively with Java

Chapter 3. Recursive Functions

To iterate is human, to recurse divine.

—Anonymous

Chapter 1 defined recursion as a solution technique that operates by reducing a large problem to simpler problems of the same type. That definition, however, does not necessarily imply the use of a computer. This chapter examines how recursion applies in the context of a programming language.

First of all, it is important to remember that the statement of any recursive solution must be general enough that it solves not only the original problem but also any subproblems generated along the way. In the context of a programming language, this requirement usually implies that the method used to represent the algorithm must take parameters that define the specific subproblem. In the case of the fundraising problem from Chapter 1, for example, it is not enough to write a single method to collect $1000 dollars. Instead, the recursive implementation solves the more general problem of raising d dollars, where d is a parameter whose value will change at different levels of the recursive solution.

Given the need to specify parameters that define a specific instance of the problem, recursive solutions usually take the form of methods whose arguments convey the necessary information. Whenever a recursive method breaks a large problem down into simpler subproblems, it solves those subproblems by calling the original method with new arguments, updated to reflect the new subproblem.

This chapter is devoted to a pair ...