Java Reference
In-Depth Information
Recursion is Common
You encounter instances of recursion every day and never think twice about them. The only notable
feature about the following sentence is that it involves a princess and a castle: “The princess lives in the
castle on the hill.” How many times have you said something similar to “I live in a red house on
Mulberry Street”?
Recursion is common in the field of computer science, too. A number of languages use recursion as
their main idiom for processing data. The most famous recursive programming language is probably
Lisp. Lisp stands for “List processing” and treats everything as a list. The usual method of processing in
Lisp is to read the first item of a list (reducing the original list), process it, read the first value of the
remaining list, process it, and so on until the list is empty. XSLT (a grandchild of Lisp through another
language called DSSSL) works in a similar way, processing XML nodes until it runs out of nodes.
All the programming languages with which I am familiar also have one mechanism or another for
supporting recursion. Recursion may be easier or harder to achieve depending on the language, but in
my experience, it's always possible.
Know Your Stop Condition
Now that you know what recursion is and have discovered that recursion is actually all around us, let's
look at how to make it work. We'll start with a problem that many software developers fear: the infinite
loop.
Recursion usually generates an infinite loop because the developer fails to check for a stop
condition or for the correct stop condition. The trouble is that the stop condition always depends on
what you're doing. If you're processing a factorial, your stop condition is the argument to the factorial
symbol. Therefore, if you're calculating 10! (10 factorial), you stop when you get to 10. Similarly, if you're
processing an XML file, the stop condition is the last child node.
The other problem is that those conditions are not similar enough for many developers. People like
to be sure of things: they don't want to have to figure out the stop condition every time. This issue often
persuades developers to avoid recursion, even when recursion is the best way to solve a problem.
Let's look at one of the examples I just mentioned, calculating a factorial:
Listing 14-1. Calculating a Factorial
package com.bryantcs.examples.factorial;
public class Factorial {
int calculate(int number) {
if (number < 0) {
throw new IllegalArgumentException("integer must be 0+");
}
if( number == 0) { return 1;
} else {
return number * calculate (number - 1);
}
}
