Thinking Recursively with Java

1.5. Thinking about Recursion—Two Perspectives

The main advantage of recursion as a solution technique is that it provides a powerful mechanism for managing complexity. No matter how difficult a problem appears, if you can find a way to break that problem down into simpler problems of the same form, you can define a strategy for producing a complete solution. As a programmer, all you need to specify is (1) how to simplify a problem by recursive subdivision, (2) how to solve the simple cases, and (3) how to reassemble the partial solutions.

Figure 1-1. Nonterminating recursion

For someone just learning about recursion, it can be hard to believe that this simple strategy is powerful enough to solve a complex problem. Given a particular problem, it is tempting to insist on seeing the solution in all its gory detail. Unfortunately, doing so has the effect of reintroducing all the complexity that the recursive definition was designed to conceal. If you give in to skepticism, the usual result is that you take a hard problem made simpler through recursion and proceed to make it difficult again. Clearly, this approach is not optimal. What you need to do instead is find a new way to think about recursion.

The difference between the perspective of the programmer with considerable experience in recursion and that of the novice is perhaps best defined in terms of the philosophical contrast ...