Java Reference
In-Depth Information
11.1
Recursive
Methods
void
I remembered too that night which is at the middle of the Thousand
and One Nights when Scheherazade (through a magical oversight of the
copyist) begins to relate word for word the story of the Thousand and
One Nights, establishing the risk of coming once again to the night
when she must repeat it, and thus to infinity.
JORGE LUIS BORGES,
The Garden of Forking Paths
When you are writing a method to solve a task, one basic design technique is to break
the task into subtasks. Sometimes it turns out that at least one of the subtasks is a
smaller example of the same task. For example, if the task is to search a list for a partic-
ular value, you might divide this into the subtask of searching the first half of the list
and the subtask of searching the second half of the list. The subtasks of searching the
halves of the list are “smaller” versions of the original task. Whenever one subtask is a
smaller version of the original task to be accomplished, you can solve the original task
by using a recursive method. We begin with a simple example to illustrate this tech-
nique. (For simplicity our examples are static methods; however, recursive methods
need not be static.)
Recursion
In Java, a method definition may contain an invocation of the method being defined. In such
cases the method is said to be
recursive
.
EXAMPLE:
Vertical Numbers
Display 11.1 contains a demonstration program for a recursive method named
to the
screen with the digits going down the screen one per line. For example, the invocation
, which takes one (nonnegative)
argument and writes that
writeVertical
int
int
writeVertical(1234);
would produce the output
1
2
3
4
(continued)
