Now that we are steeped in trees, we can look back at Figures 4.2 and 4.4 and notice that they are pictures of trees. We shall call them the execution trees of their corresponding recursive programs. In fact, any recursive program can be viewed as generating such a tree as it executes. The recursive program can be thought of as executing by traversing its corresponding execution tree. The processing done at each node in the course of this traversal is the carrying out of the program's task on a specific problem specified by its data and current scratchpad. Now that you know a good deal about tree traversals, is it any wonder that the stack appears in the translation of a recursive program? It is clearly the number of nodes in the tree that determines the execution time of the algorithm, and it is the depth of the tree that determines the storage requirements. This point can become somewhat muddled when recursion is applied to trees themselves, but you should realize that this is the case even when no trees are apparent in the nature of the problem, as in the Towers of Hanoi problem in Chapter 4.
Further, we can now see that recursion clarifies because it hides the bookkeeping required by the tree traversal and because it elucidates the structure that must be inherent in the problem in order for a recursive solution to be found in the first place. Although it is an extremely powerful tool for these reasons, it must be applied with care. The purpose of this section is to provide some insight into the nature of those problems where a more skeptical approach is wise.
7.7.2 Trading Storage for Time