[This page is auto-generated; please prefer to read the article’s PDF Form.]
Suppose there is a recursive method recur(). We want to create a variant of this which does not call itself and maintains its own stack to simulate the recursive calls. Thus recursion will still take place, but via our own stack instead of the one used for the program execution.
In this article, we will figure out how this can be done and apply it to a simple example. Further details may need to be worked out based on the given situation. We will refer to the new variant method as recur_stack(), the stack it will maintain as vc_stack (“virtual-call stack”), and the recursive calls which will get simulated now on this stack as “virtual-calls”. The stack used for general function calls during program execution will be referred as “program-stack”.
We can bring some ideas from the program-stack. So let us briefly look at how it works. It consists of stack-frames where each frame corresponds to an individual call. The order of frames on the stack is according to the order of calls which have been made till the current executing function, which corresponds to the top of the stack. Each frame is used to record the state of the individual call, which generally includes the local variables, input arguments, and instruction location to resume execution when the called function returns.
We will try to find out what kind of facilities are needed for simulating the recursive calls on our own stack.
[Next]
Copyright © 2020 Nitin Verma. All rights reserved.