Up: Recursion. Prev: A solution program. Next: Recurrences.

Tracing our Towers solution

To use this trace, just keep clicking on the ``Make one step'' button. You can use the ``Finish this call'' button to skip to the step after finishing the current level.

The call stack in the display above represents where we are in the recursion. It keeps track of the different levels going on. The current level is at the bottom in the display. When we make a new recursive call, we add a new level to the call stack representing this recursive call. When we finish with the current level, we remove it from the call stack (this is called popping the stack) and continue with where we left off in the level that is now current.

Another way to visualize what happens when you run MoveTower is called a call tree. This is a graphic representation of all the calls. Here is a call tree for MoveTower(3,A,B,C).

We call each function call in the call tree a node. The nodes connected just below any node n represent the function calls made by the function call for n. Just below the top, for example, are MoveTower(2,A,C,B) and MoveTower(2,C,B,A), since these are the two function calls that MoveTower(3,A,B,C) makes. At the bottom are many nodes without any nodes connected below them - these represent base cases.

Make sure you understand our MoveTower program well. Now we ask: If the monks use MoveTower, how long is it before the world ends? To answer this question, we need to learn about recurrences.

Next: Recurrences.