As has been pointed out in this thread elsewhere, it _sometimes_ requires that you implement your own stack, which by some definitions _might_ constitute recursion.
So, if you want to know if you can always do away with a stack, the answer is no. Sometimes, but not always.
But you can still make it iterative, avoiding the need for specifically a function call stack as per the compiler, and avoiding the need for a function to call itself.
It is, quite often, faster than the recursive version because of the overhead of pushing parameters, popping return values, and other bits of stack maintenance. You may still have to do your own stack maintenance, but often the overhead is far far less as it can be tuned to your particular algorithm.
A recursive version of quicksort I wrote, and an iterative version (that, yes, had to use a stack), definitely timed in favour of the iterative solution.
One can reduce the overhead of the recursion through careful selection of the parameters you pass, of course.
As to a general algorithm, that's straightforward:
Ordinary functional recursion stashes the 'state of the function' at the point of the recursive call, on a stack S, so that that state may be returned to after the recursive call has returned.
You can emulate this by writing your function this way:
1) Create a structure that maintains all of the state of operation of your function. Use no local variables - instead, put them in this struct, let's call it struct Q, and have a local variable of type Q, call it q. All of your local variables are manipulated within q.
(You can do without actually stuffing it in a structure, by handling individual variables, but it makes the process below easier to describe).
2) Break down your program into regions of code that can be uniquely identified, say with an integer, that are broken up by recursive calls. You need to store, in Q, an integer, or enumeration, or some sort of tag saying in what _part_ of your code you were when you made the recursive call so you can pick up where you left off. So your function has to be broken down into 'states'. It could be simple, like:
if (q.state==0)
{
/*do something*/
}
if (q.state==1)
{
/*do something*/
}
if (q.state==2)
{
/*do something*/
}
In theory, you could identify every individual line or instruction in your function this way, but of course, in a practical implementation, you'd group stages that are not interrupted by recursion. In fact, basically you group statements that are before or after a recursive call.
Depending on how you implement this, it might be nice to have a final state for q.state representing 'stop'.
3) Whenever you do a recursion, advance q.state to be the code right after the recursion, push a copy of q onto S, which stores the entire state of your function, including where you were in that function. Then alter q to represent the new state of the function for the subproblem by altering the local variables inside q, including resetting the state to 0, to represent the start of the function.
4) Whenever you finish a level of recursion, pop the top element of the stack S back into q to restore the program state, which includes which state you wanted to go into after the recursion.
5) Wrap the whole shebang in a loop that iterates as long as the queue is not empty and the current state q.state is not your final stop state. Alternately, write the loop to just test for an empty queue, and before the loop, push on a q containing a q.state that is a special start state, and then pop it off as a special case in the loop.
That's basically it, in too many words. This is the worst case scenario: Maintain and restore the state of your function's operations, in total, including all local variables and the 'position in the code', as you enter and leave your simulated recursion.
Now, in practice, you can get away with far far less than this. You might get away with having no stack, or a stack which only needs to have a very small subset of the local variables pushed and popped. You might not need a 'function state counter', as it might be implicit in the variables you're using. Or, you might need a state, but might be a single bool.
But you asked if there's a general technique, and this kinda outlines it.
|
