Java Reference
In-Depth Information
11
Recursion
After a lecture on cosmology and the structure of the solar system, William
James was accosted by a little old lady.
“Your theory that the sun is the center of the solar system, and the earth is a
ball which rotates around it has a very convincing ring to it, Mr. James, but
it's wrong. I've got a better theory,” said the little old lady.
“And what is that, madam?” inquired James politely.
“That we live on a crust of earth which is on the back of a giant turtle.”
Not wishing to demolish this absurd little theory by bringing to bear the
masses of scientific evidence he had at his command, James decided to
gently dissuade his opponent by making her see some of the inadequa-
cies of her position.
“If your theory is correct, madam,” he asked, “what does this turtle stand on?”
“You're a very clever man, Mr. James, and that's a very good question” replied
the little old lady, “but I have an answer to it. And it is this: the first turtle
stands on the back of a second, far larger, turtle, who stands directly
under him.”
“But what does this second turtle stand on?” persisted James patiently.
To this the little old lady crowed triumphantly. “It's no use, Mr. James—it's
turtles all the way down.”
J. R. ROSS,
Constraints on Variables in Syntax
Introduction
A method definition that includes a call to itself is said to be
. Like most mod-
ern programming languages, Java allows methods to be recursive, and if used with a little
care, this can be a useful programming technique. In this chapter we introduce the basic
techniques needed for defining successful recursive methods. There is nothing in this
chapter that is truly unique to Java. If you are already familiar with recursion you can
safely skip this chapter. No new Java elements are introduced in this chapter.
recursive
recursive
method
Prerequisites
Except for the last subsection on binary search, this chapter uses material only from
Chapters 1-5. The last subsection entitled “Binary Search” also uses the basic material
on one-dimensional arrays from Chapter 6.
You may postpone all or part of this chapter if you wish. Nothing in the rest of this
book requires any of this chapter.
