Recursion - Java Software Solutions: Foundations of Program Design - page 584

12.1 Recursive Thinking

We've seen many times in previous examples that one method can
call another method to accomplish a goal. What we haven't seen yet,
however, is that a method can call itself. Recursion is a program-
ming technique in which a method calls itself in order to fulfill its
purpose. But before we get into the details of how we use recursion
in a program, we need to explore the general concept of recursion.
The ability to think recursively is essential to being able to use recur-
sion as a programming technique.
In general, recursion is the process of defining something in terms of itself. For
example, consider the following definition of the word

KEY CONCEPT
Recursion is a programming tech-
nique in which a method calls itself.
The key to being able to program
recursively is to be able to think
recursively.

decoration :
decoration : n. any ornament or adornment used to decorate something

The word decorate is used to define the word decoration . You may recall your
grade school teacher telling you to avoid such recursive definitions when explain-
ing the meaning of a word. However, in many situations, recursion is an appro-
priate way to express an idea or definition. For example, suppose we wanted
to formally define a list of one or more numbers, separated by commas. Such a
list can be defined recursively as either a number or as a number followed by a
comma followed by a list. This definition can be expressed as follows:

A List is a: number

or a: number comma

List

This recursive definition of List defines each of the following lists of numbers:

24, 88, 40, 37
96, 43
14, 64, 21, 69, 32, 93, 47, 81, 28, 45, 81, 52, 69
70

No matter how long a list is, the recursive definition describes it. A list of one
element, such as in the last example, is defined completely by the first (non-recur-
sive) part of the definition. For any list longer than one element, the recursive part
of the definition (the part which refers to itself) is used as many times as necessary
until the last element is reached. The last element in the list is always defined by
the non-recursive part of the definition. Figure 12.1 shows how one particular list
of numbers corresponds to the recursive definition of List .

Infinite Recursion
Note that the definition of List contains one option that is recursive and one
option that is not. The part of the definition that is not recursive is called the base