Java Reference
In-Depth Information
Note:
Recursion is a problem-solving process that breaks a problem into identical but
smaller problems.
Ultimately, we have a group of napping people waiting for someone to say “I'm done.” The
first person to make that claim is the person who shouts “1,” as Figure 7-1 illustrates, since that per-
son needs no help in counting down from 1. At this time in this particular example, the problem is
solved, but I don't know that because I'm still asleep. The person who shouted “1” says “I'm done”
to the person who shouted “2.” The person who shouted “2” says “I'm done” to the person who
shouted “3,” and so on, until you say “I'm done” to me. The job is done; thanks for your help; I
have no idea how you did it, and I don't need to know!
7.3
What does any of this have to do with Java? In the previous example, you play the role of a Java
method. I, the client, have asked you, the recursive method, to count down from 10. When you ask
a friend for help, you are invoking a method to count down from 9. But you do not invoke another
method; you invoke yourself!
Note:
A method that calls itself is a
recursive method
. The invocation is a
recursive call
or
recursive invocation
.
The following Java method counts down from a given positive integer, displaying one integer
per line.
/** Counts down from a given positive integer.
@param integer an integer > 0 */
public static void
countDown(
int
integer)
{
System.out.println(integer);
if
(integer
>
1)
countDown(integer - 1);
}
// end countDown
Since the given integer is positive, the method can display it immediately. This step is analogous to
you shouting “10” in the previous example. Next the method asks whether it is finished. If the
given integer is 1, there is nothing left to do. But if the given integer is larger than 1, we need to
count down from
integer
-
1. We've already noted that this task is smaller but otherwise identical
to the original problem. How do we solve this new problem? We invoke a method, but
countDown
is such a method. It does not matter that we have not finished writing it at this point!
7.4
Will the method
countDown
actually work? Shortly we will trace the execution of
countDown
both
to convince you that it works and to show you how it works. But traces of recursive methods are
messy, and you usually do not have to trace them. If you follow certain guidelines when writing a
recursive method, you can be assured that it will work.
In designing a recursive solution, you need to answer certain questions:
Note:
Questions to answer when designing a recursive solution
•
What part of the solution can you contribute directly?
•
What smaller but identical problem has a solution that, when taken with your contribution,
provides the solution to the original problem?
•
When does the process end? That is, what smaller but identical problem has a known
solution, and have you reached this problem, or
base case
?
