Thinking Recursively with Java

Chapter 11. Implementing Recursion

Never trust to general impressions, my boy, but concentrate yourself upon details.

—Sir Arthur Conan Doyle, A Case of Identity, 1891

Up to this point, this book has been concerned with developing a strategy for recursive programming based on a high-level understanding of the underlying mechanism. For the person who shares with Sherlock Holmes a desire to reduce a problem to its smallest details, it is important to consider the implementation of recursion from a more intimate perspective.

The discussion of the Tower of Hanoi puzzle in Chapter 5 offered a conceptual model for the implementation of recursion using a stack of index cards to manage the necessary bookkeeping operations. When faced with a recursive implementation, a computer system must keep track of the same sort of information in its internal storage. More specifically, the computer must keep track of the following information for every method call:

1. The values of all local variables for this method, making sure that the new set of values do not interfere with those in any as-yet-unfinished call

2. The point in the program at which this method call was made so that execution can continue from the proper point when this method returns.

What makes this bookkeeping difficult is the fact that the computer must maintain this information for each level in the recursive decomposition simultaneously. Calling a method introduces a new environment that temporarily supersedes the preceding one. When ...