Java Reference
In-Depth Information
C H A P T E R 1 4
Recursion
Recursion has an undeserved reputation for being hard to do and hard to control. For various reasons,
many developers have trouble using recursion as one of their programming tools. I suspect the difficulty
stems from two predicaments: having to give up control so that the recursive classes or methods can do
their work and not being able to “see” the recursion work (though the debugger can solve the latter
problem). Also, the first try at recursion usually ends poorly, resulting in an infinite loop (that is, a
process that never stops), and software developers are trained to be very wary of infinite loops. All of
these problems can be overcome with surprisingly easy-to-use and easy-to-understand techniques,
which I'll address later in the chapter.
Before I dive into how to work with recursions, though, let's take a close look at what recursion is.
Recursion is Natural
The main reason I am surprised that so many developers distrust recursion is that recursion is a feature
of human language. We all use it every day when we talk to one another. English utilizes recursion in a
number of situations. One of the rules (from the field within Linguistics called Transformational
Grammar, which I studied in college) of the English language is that one sentence can be embedded into
another sentence. I won't dive into the sentence diagrams to prove it, but I'll give you an example in the
form of a children's rhyme from long ago:
This is the house that Jack built.
This is the malt that lay in the house that Jack built.
This is the rat that ate the malt that lay in the house that Jack built.
As you can see, kids can keep going for as long as they can think of things to add (or until their
parents yell at them to stop). English supports recursion in other situations as well. For instance, another
rule in English is that we can stack up prepositional phrases as deep as we like, thus:
The princess lives in the castle.
The princess lives in the castle on the hill.
The princess lives in the castle on the hill by the road.
The princess lives in the castle on the hill by the road in the swamp.
Again, we can keep doing this for as long as it amuses us to do so.
