Up: Recursion. Prev: A solution program. Next: Recurrences.
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).
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.