Maintaining the Stack for Recursion: Iterations and Frames

[This page is auto-generated; please prefer to read the article’s PDF Form.]

[Prev] [Up] [Next]

Iterations and Frames

Here is how the vc_stack and iterations will work together. At the beginning of recur_stack(), we set up the vc_stack with only one frame which speciﬁes the state to use for the very ﬁrst virtual-call. After this, we start the iterations. At the beginning of each iteration, we will read the topmost frame of vc_stack, which becomes the current frame for that iteration. Then we execute some logic in the iteration according to the state speciﬁed in the current frame.

When a recursive virtual-call has to be made, we will make any necessary updates in the current frame, setup the frame for the new call with its input arguments, push it on the vc_stack, and continue with a new iteration. In the new iteration, the new call would execute afresh.
When the current virtual-call has to return, we will pop its frame from top of the vc_stack, and continue with a new iteration. In the new iteration, we resume execution of its “caller” using the caller’s own frame (which is top of the stack now).

[Prev] [Up] [Next]