Visit a tree or graph structure using tail recursion

Question

Let's say I have a structure to visit in a recursive way.

Pseudocode:

visit(node n)
{
    if (n == visited)
         return;

    //do something
    setVisited(n);
    foreach child_node in n.getChildren(){
        visit(child_node);
    }

}

According to this thread tail recursion can occured when:

Tail recursion is basically when:

• there is only a single recursive call
• that call is the last statement in the function

In the pseudocode above the recursive call is the last statement, but there are multiple recursive call since the call happens inside a loop. I guess no tail recursion could be detected by the compiler.

My question is:

is there anyway to refactor the code above in order to make it tail recursive? I'm looking for a solution that doesn't remove the recursion, if there is one (es. I don't want to use a stack to simulate the recursion and transform that into an iterative function).

is this possible?

If the language is relevant, I'm using C++.

Answer 1

So, in fact you can always refactor a function to be tail recursive... Most of the people programming in other languages will use continuation to code it efficiently. But, we are looking here at C/C++ language more specifically, so I assume to get rid of this just by coding the function itself (I mean without adding a generic continuation framework to the language).

Lets suppose that you have an iterative version of your function which should look like this:

void iterative() {
  while (cond)
    dosomething()
}

Then, turning it into a tail recursive function is simply done by writing:

void tailrecursive() {
  if (!cond)
    return;

  dosomething();
  tailrecursive();
}

Most of the time, you need to pass a 'state' to the recursive call which adds some extra parameters that were not useful before. In your specific case, you have a preorder tree traversal:

void recursive_preorder(node n) {
  if (n == visited)
    return;

  dosomething(n);
  foreach child_node in n.getChildren() {
    recursive_preorder(child_node);
  }
}

The iterative equivalent needs to introduce a stack to remember the explorer nodes (so, we add push/pop operations):

void iterative_preorder(node n) {
  if (n == visited)
    return;

  stack worklist = stack().push(n);
  while (!worklist.isEmpty()) {
    node n = worklist.pop()
    dosomething (n);
    foreach child_node in n.getChildren() {
        worklist.push(child_node);
    }
  }
}

Now, taking this iterative version of the preorder tree traversal and turning it into a tail recursive function should give:

void tail_recursive_preorder_rec(stack worklist) {
  if (!worklist.isEmpty()) {
    node n = worklist.pop()
    dosomething (n);
    foreach child_node in n.getChildren() {
        worklist.push(child_node);
    }
  }
  tail_recursive_preorder_rec(worklist)
}

void tail_recursive_preorder (node n) {
  stack worklist = stack().push(n);
  tail_recursive_preorder_rec(worklist);
}

And, it gives you a tail recursive function that will be nicely optimized by the compiler. Enjoy!

Answer 2

I don't think you can. Tail recursion basically shortcuts various bits of function calling procedure in order to avoid unnecessary cost in the situation where after the call returns the calling function also immediately returns. However, in this case at any given recursion level you're making (potentially) multiple calls, so you need to be able to return from those calls and then make another, which is not a tail recursion scenario. The most you could hope for is that the last one gets optimised as a tail call, but I doubt the compiler can detect that because as you say it's inside a loop and the data you're iterating over is not known at compile time.

I can't think of a way to alter the algorithm to make it tail-recursive - you're always going to have that potential for multiple children which mucks it up.