Java 7 for Absolute Beginners

CHAPTER 14 ■ RECURSION

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);

}

}