Recursion - Absolute Java - page 649

You may postpone all or part of this chapter if you wish. Nothing in the rest of this
book requires any of this chapter.
11.1 Recursive void Methods
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 particular 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 technique. (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
writeVertical , which takes one (nonnegative) int argument and writes that int
to the screen with the digits going down the screen one per line. For example, the
invocation
writeVertical(1234);
would produce the output
1
2
3
4
(continued)