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++.

perror · Answer 1 · 2017-08-23T16:13:16.337

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!

Great answer! Is it true that any primitive recursive function can be translated to tail rec ? — doofin, Sep 26 '20 at 11:36
Yes, but is has some cost. Because, you need to carry over all the information that you keep on the stack. So, some problems are more suitable for being translated to primitive recursive and some others are just hell. — perror, Sep 28 '20 at 15:30
What if a parent needs data from the child? i.e. call the recursive function on each child and when each child completes, do something with that result. Like finding bridges in a graph. — Mayur, Jan 10 '21 at 11:30

score 2 · Answer 2 · answered Jan 23 '12 at 11:16

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.

score 1 · Accepted Answer · edited May 23 '17 at 12:20

1

Tail recursion is immitating loops with no stack [or any other data structure], i.e. O(1) additional space.

AFAIK, the problem at hand, of tree/graph traversal [assume no parent field in each node] cannot be done at such a complexity [O(n) time, O(1) space], thus cannot be done with a single loop, with no stack. Therefore, no tail recursion refactoring is possible.

EDIT: The problem can be solves in O(1) space, but with O(n^2) time [which is double loop], as seen in this post.

edited May 23 '17 at 12:20

Community

1
1

answered Jan 23 '12 at 11:22

amit

175,853
27
231
333

1

@amit: Hum, what you say is just totally wrong... You can always refactor to tail recursion (especially when you have an iterative version at hand nearby). – perror Aug 23 '17 at 15:27

Visit a tree or graph structure using tail recursion

3 Answers3