handling the tail part of a non-tail recursive function when converting it to an iterative function

Question

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?

Answer 1

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.

Answer 2

A general approach to convert recursion into iteration it to use a kind of event loop that repetedly pops events from a stack and executes their handlers. I'm going to first write some pseudocode which is similar to your recursive function, so it will be easier to understand the conversion:

recurse (node)
{
    for (i = 0; i < 4; i++) {
        if (condition(node, i)) {
            recurse(next_node(node, i));
        }
    }
}

What we do now is split this recursive function into a sequence of operations - however, instead of writing it explicitly, we define each operation as an event and its corresponding event handler, and in case there is more work to be done after this operation, the handler will push this further work to the stack prior to performing its operation.

my_iterative_function ()
{
    // build the event stack and push the initial event
    EventStack stack;
    stack.push(NewRecurseEvent(node = first_node));

    // pop and execute events
    while (!stack.isEmpty()) {
        Event ev = stack.pop();
        ev.executeHandler();
    }
}

RecurseEventHandler (node)
{
    // We are at the beginning of the "recurse" function.
    // Push iteration 0 (we could optimize this and just do it here).
    stack.push(NewIterationEvent(node = node, i = 0));
}

IterationEventHandler (node, i)
{
    // Unless this is the last iteration, push the next iteration
    // to be executed after this iteration is complete. It will work
    // with the same node, but 'i' one greater.
    if (i < 3) {
        stack.push(NewIterationEvent(node = node, i = i + 1));
    }

    // do the work of this iteration
    if (condition(node, i)) {
        # Initiate the recursion by pushing.
        # It is crutial to understand that the event loop will pop this event,
        # and all events pushed by it, recursively, before
        # popping the continuation event we pushed above.
        # That is, it will behave just like the recursive variant.
        stack.push(NewRecurseEvent(node = next_node(node, i)));
    }
}

It depends on the language how to actually implement this pseudocode. In C, the event object can be a tagged union that holds arguments to various event handlers, and you can have the event loop just directly perform the event handler actions:

struct event {
    int type; // RECURSE_EVENT or ITERATION_EVENT
    union {
        struct {
            node node;
        } recurse_event;
        struct {
            node node;
            int i;
        } iteration_event;
    };
};

while (!stack.isEmpty()) {
    struct event ev = stack.pop();
    switch (ev.type) {
        case RECURSE_EVENT: {
            node n = ev.recurse_event.node;
            ...
        } break;
        case ITERATION_EVENT: {
            node n = ev.iteration_event.node;
            int i = ev.iteration_event.i;
            ...
        } break;
    }
}

Since your actual recursive function is more complex than my simple example because of the part that follows the recursive call, you will need more events to handle this. For example, you can add another kind of event to handle the post-recursion step:

IterationEventHandler (node, i)
{
    if (i < 3) {
        stack.push(NewIterationEvent(node = node, i = i + 1));
    }

    if (condition(node, i)) {
        // This PostEvent will be executed after the recursive work,
        // but before the next iteration pushed above.
        stack.push(NewPostEvent(node = node, i = i));
        stack.push(NewRecurseEvent(node = next_node(node, i)));
    }
}

PostEventHandler (node, i)
{
    // do your post-recursion work here
}

It is easy to understand this if you consider that, when looking at a single event handler, all work will be performed in the reverse order it was pushed. For example, at the IterationEventHandler above, first the recursion will be performed, then the post-recursion step, and finally the next iteration step will begin (if at all). In even simpler terms, each push can be understood as a possibly-recursive function call, except that these calls would execute from the bottom up.

Do note that this is a general approach. It is probably possible to build a compiler that converts any recursive function into such an event loop. Also, this approach is not only an elegant way to convert recursion into iteration; the "stack event loop" idea is very practical in design of event-driven software, particularly so if you also have the ability to dequeue events that have been pushed but not yet executed. I've explained this in my answer to this question.