Thinking Recursively with Java

1.3. Characteristics of Recursive Algorithms

In each of the examples so far, finding simpler subproblems within the context of a larger problem was a reasonably easy task. These problems are naturally suited to the "divide-and-conquer" strategy, which makes recursive solutions particularly appropriate.

In most cases, the decision to use recursion is suggested by the nature of the problem. However, it is important to recognize that "recursiveness" is a property of the solution to a problem and not an attribute of the problem itself. To be an appropriate candidate for recursive solution, a problem must have three distinct properties:

1. It must be possible to decompose the original problem into simpler instances of the same problem.

2. As the large problem is broken down into successively less complex ones, those subproblems must eventually become so simple that they can be solved without further subdivision.

3. Once each of these simpler subproblems has been solved, it must be possible to combine these solutions to produce a solution to the original problem.

For a problem with these characteristics, the recursive solution proceeds in a reasonably straightforward way. The first step consists of checking to see whether the problem fits into the simple-case category. If it does, you can solve the problem directly. If not, you need to break the entire problem down into new subsidiary problems that have the same form as the original problem. To solve each of these subproblems, all you need to ...