Recursion - Data Structures and Problem Solving Using Java - page 294

what is recursion?

7.1

A recursive method is a method that either directly or indirectly makes a call to
itself. This action may seem to be circular logic: How can a method F solve a
problem by calling itself? The key is that the method F calls itself on a differ-
ent, generally simpler, instance. The following are some examples.

A recursive method
is a method that
directly or indi-
rectly makes a call
to itself.

Files on a computer are generally stored in directories. Users may
create subdirectories that store more files and directories. Suppose
that we want to examine every file in a directory D , including all files
in all subdirectories (and subsubdirectories, and so on). We do so by
recursively examining every file in each subdirectory and then exam-
ining all files in the directory D (discussed in Chapter 18).

n

Suppose that we have a large dictionary. Words in dictionaries are
defined in terms of other words. When we look up the meaning of a
word, we might not always understand the definition, so we might
have to look up words in the definition. Likewise, we might not
understand some of those, so we might have to continue this search
for a while. As the dictionary is finite, eventually either we come to a
point where we understand all the words in some definition (and thus
understand that definition and can retrace our path through the other
definitions), we find that the definitions are circular and that we are
stuck, or some word we need to understand is not defined in the dic-
tionary. Our recursive strategy to understand words is as follows: If
we know the meaning of a word, we are done; otherwise, we look the
word up in the dictionary. If we understand all the words in the defini-
tion, we are done. Otherwise, we figure out what the definition means
by recursively looking up the words that we do not know. This proce-
dure terminates if the dictionary is well defined, but it can loop indef-
initely if a word is circularly defined.

n

Computer languages are frequently defined recursively. For instance,
an arithmetic expression is an object, or a parenthesized expression,
or two expressions added to each other, and so on.

n

Recursion is a powerful problem-solving tool. Many algorithms are most eas-
ily expressed in a recursive formulation. Furthermore, the most efficient solutions
to many problems are based on this natural recursive formulation. But you must
be careful not to create circular logic that would result in infinite loops.
In this chapter we discuss the general conditions that must be satisfied by
recursive algorithms and give several practical examples. It shows that some-
times algorithms that are naturally expressed recursively must be rewritten
without recursion.