Recursion - Data Structures and Abstractions with Java - page 157

For the method countDown , we have the following answers to these questions:

•

The method countDown displays the given integer as the part of the solution that it contributes
directly. This happens to occur first here, but it need not always occur first.

•

The smaller problem is counting down from integer - 1. The method solves the smaller
problem when it calls itself recursively.

• The if statement asks if the process has reached the base case. Here the base case occurs

when integer is 1. Because the method displays integer before checking it, nothing is left
to do once the base case is identified.

Note: Design guidelines for successful recursion
To write a recursive method that behaves correctly, you generally should adhere to the fol-
lowing design guidelines:

•

The method must be given an input value, usually as an argument, but sometimes as a
value read.

•

The method definition must contain logic that involves this input value and leads to differ-
ent cases. Typically, such logic includes an if statement or a switch statement.

• One or more of these cases should provide a solution that does not require recursion.

These are the base cases, or stopping cases .

•

One or more cases must include a recursive invocation of the method. These recursive
invocations should in some sense take a step toward a base case by using “smaller”
arguments or solving “smaller” versions of the task performed by the method.

Programming Tip: Infinite recursion
A recursive method that does not check for a base case, or that misses the base case, will exe-
cute “forever.” This situation is known as infinite recursion.

7.5

Before we trace the method countDown , we should note that we could have written it in other ways.
For example, a first draft of this method might have looked like this:
public static void countDown( int integer)
{

if (integer == 1)
System.out.println(integer);
else
{

System.out.println(integer);
countDown(integer - 1);
} // end if
} // end countDown
Here, the programmer considered the base case first. The solution is clear and perfectly acceptable,
but you might want to avoid the redundant println statement that occurs in both cases.

7.6

Removing the redundancy just mentioned could result in either the version given earlier in
Segment 7.3 or the following one:

public static void countDown( int integer)
{