When converting a non-tail recursive function to an iterative function using your own made stack what is the general approach to take care of the part of the code that comes after the recursion call aka the tail?
The following function is supposed to explore all the possible paths in a maze, revisiting a previsited path in order to visit other paths in the stack:
struct node{
int id;
bool free;
int neighborNode[4];
int toProcess;
} nodeMap[100];
void findPath(int current){
visited[current] = true;
int i;
for (i=0; i < 4; i++){
if(nodeMap[nodeMap[current].neighborNode[i]].free == true && visited[nodeMap[current].neighborNode[i]] == false && nodeMap[current].neighborNode[i] != -1){
path[cc] = nodeMap[nodeMap[current].neighborNode[i]].id;
cc++;
findPath(nodeMap[current].neighborNode[i]);
path[cc] = nodeMap[current].id;
cc++;
}
}
}
The recursive part of the code is easily convertible to an iteration (I have used a field toProcess to imitate the index of the loop cause it is not saved in the stack and is needed for processing all the childs):
void findPath(){
if (isEmpty())
return;
else {
node temp = pop();
visited[temp.id] = true;
if (temp.toProcess < 3) {
temp.toProcess++;
push(temp);
temp.toProcess--;
}
if(nodeMap[temp.neighborNode[temp.toProcess]].free == true && visited[temp.neighborNode[temp.toProcess]] == false && temp.neighborNode[temp.toProcess] != -1){
path[cc] = nodeMap[temp.neighborNode[temp.toProcess]].id;
cc++;
push(nodeMap[temp.neighborNode[temp.toProcess]]);
}
}
}
But the part where the algorithm moves backwards to revisit previously seen nodes to explore other possible paths (the tail) i.e. path[cc] = nodeMap[current].id; & cc++; does not seem to fit in the iterative version of the method!
Is there a general approach to this? Or every case is different? In anyways, do you have any suggestion how to implement the tail part in this case?
The stack solution is nice and easy with tail-recursive functions, but as in your example, since you are doing something after the recursive call, you need to figure out a way to perform those operations after the call has ended.
The following is a possible solution:
struct stack_element
{
... your_stuff...
bool expanded;
};
In the code:
stack_element e;
... fill e
e.expanded = false;
push(e);
while (!empty())
{
e = pop();
if (e.expanded)
{
... do the stuff that was supposed to be done
... after e and all its children are processed
}
else
{
e.expanded = true;
push(e); // push e, so it would be visited again
// once all children are processed
for (every child of e)
if (they met the conditions)
{
... do the stuff before
stack_element child;
... fill child
child.expanded = false;
push(child);
}
}
}
What this basically does is, visits each node twice. Once when being expanded, at which point you execute the stuff before the recursive call, and another time once all its children have finished processing, at which point you execute the stuff after the recursive call.
Note that, you may need to save some states, such as maybe cc and current along with the node, so that you would be able to do the if (e.expanded) part correctly.
Side suggestion: Use a for loop as you have done in the recursive method, which is more clear than using toProcess.
In your case, that execution on one branch of children affects visiting or not visiting the others, you can follow the following approach:
Each time you get a node, check if it meets the necessary conditions. If it does, do the processing before the call of that node. Then like before, push it again so it will be visited again and the post-processing would be done. This way, every time you just push the children, and later decide if they are good or not:
struct stack_element
{
... your_stuff...
bool expanded;
... save also cc, current and i
};
stack_element e;
... fill e
e.expanded = false;
push(e);
while (!empty())
{
e = pop();
if (e.expanded)
{
... do the stuff that was supposed to be done
... when function called with e is returning and
... after the function returns to parent
}
else if (conditions for are met)
{
... do the stuff that was supposed to be done before
... e is recursively called and at the beginning of the
... function
e.expanded = true;
push(e); // push e, so it would be visited again
// once all children are processed
for (every child of e, in reverse order)
{
stack_element child;
... fill child
child.expanded = false;
push(child);
}
}
}
After looking at the exact code, here's the converted version:
struct stacknode{
int id;
int parent;
bool free;
bool expanded;
};
int cc = 0;
void findPath2(int current){
// special case for the first call:
visited[current] = true;
// expand the first node, because when the first node is popped,
// there was no "stuff before recursion" before it.
int i;
for (i=3; i >= 0; --i){
// Put the neighbors on the stack so they would be inspected:
stacknode child;
child.id = nodeMap[current].neighborNode[i];
child.parent = current;
child.free = nodeMap[child.id].free;
child.expanded = false;
push(child);
}
while (!isEmpty())
{
stacknode cur = pop();
if (cur.expanded == true)
{
// Now, it's like a return from a recursive function
// Note: cur.id will be nodeMap[current].neighborNode[i] because that was the value the function was called with
// Stuff at the end of the function:
path[0]=current; // Note: this is kind of absurd, it keeps getting overwritten!
// Stuff after recursion:
cc++; // note that path[0] is reserved for first node, so you should first increment cc, then set path[cc]
path[cc] = nodeMap[cur.parent].id; // nodeMap[current].id: current was the parent of
// nodeMap[current].neighborNode[i] for which the function was called
}
else
{
// Now, it's like when the recursive function is called (including stuff before recursion)
// Note: cur.id will be nodeMap[current].neighborNode[i] because that was the value the function was called with
// Check whether child was supposed to be added:
if(cur.id != -1 && nodeMap[cur.id].free == true && visited[cur.id] == false)
// Node: Put cur.id != -1 in the beginning. Otherwise, you would possibly check
// nodeMap[-1] and visited[-1] which is not nice
{
cur.expanded = true;
push(cur);
// Stuff before recursion:
cc++;
path[cc] = nodeMap[cur.id].id; // in cur.id, nodeMap[current].neighborNode[i] was stored
// Stuff at the beginning of function call:
visited[cur.id] = true;
// The body of the function:
for (i=3; i >= 0; --i){
// Put the neighbors on the stack so they would be inspected:
stacknode child;
child.id = nodeMap[cur.id].neighborNode[i];
child.parent = cur.id;
child.free = nodeMap[child.id].free;
child.expanded = false;
push(child);
}
}
}
}
// end of special case for first call:
path[0] = current;
}
Note that the reason it starts to get complicated is the existence of cc which is a global variable. If you had a recursive function that didn't use global variables, the conversion would have been simpler.