Thinking Recursively with Java

1.4. Nonterminating Recursion

In practice, the process of ensuring that a particular decomposition of a problem will eventually result in the appropriate simple cases requires a certain amount of care. If this is not done correctly, recursive processes may get locked into cycles in which the simple cases are never reached. When this situation occurs, a recursive algorithm fails to terminate, and a program that is written in this way will continue to run until it exhausts the available resources of the computer.

For example, suppose that, as campaign fundraiser, you decided instead to collect the $1000 using the following strategy:

Find a single volunteer who will collect $1000.

If you adopted this strategy, and every volunteer you found did the same, the process would continue until the available pool of volunteers was exhausted, even though you had raised no money at all. A more fanciful example of this type of failure is illustrated by the classic children's song "There's a Hole in the Bucket," as shown in Figure 1-1.