Visiting a tree or graph structure using tail recursion

Question

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

pseudo code:

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 happen when:

Tail recursion is mainly when:

• there is only one recursive call
• this call is the last in function

In the pseudocode above, a recursive call is the last statement, but there are several recursive calls, since the call occurs inside the loop. I think that no tail recursion can be detected by the compiler.

My question is:

In any case, in order to reorganize the code above to make it tail recursive? I am looking for a solution that does not remove recursion if there is one (for example, I do not want to use the stack to simulate recursion and convert to an iterative function).

Is it possible?

If the language is relevant, I use C ++.

Answer 1

Tail recursion is the encoding of loops without a stack [or any other data structure], i.e. O(1) extra space.

AFAIK, the problem with tree / graph traversal [assuming that not parent in each node] cannot be performed with such complexity [ O(n) time, O(1) space]), therefore it cannot be executed by one circuit, without a stack . Therefore, tail-recursion refactoring is not possible.

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

Answer 2

I do not think you can. Tail recursion basically combines the various bits of the function call procedure to avoid unnecessary cost in a situation where the calling function returns after the call also returns immediately. However, in this case, at any given level of recursion, you make (potentially) several calls, so you need to be able to return from these calls, and then make another one that is not a tail recursion script. The best you can hope for is that the latter gets optimized as a tail call, but I doubt that the compiler can detect this because, as you say, inside the loop and the data you are repeating at compile time unknown.

I cannot think of how to change the algorithm to make it tail recursive - you will always have such potential for several children who are happy with it.

Answer 3

So, in fact, you can always reorganize a function into tail recursion ... Most people programming in other languages ​​will use a sequel to code it effectively. But we look in more detail here in C / C ++, so I assume that I get rid of this simply by coding the function itself (I mean without adding a general basis for the continuation to the language).

Suppose 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(); } 

In most cases, you need to pass the “state” to a recursive call, which adds additional parameters that were not previously useful. In your specific case, you have a pre-order 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 should introduce a stack to memorize 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 pre-order tree traversal and turning it into a tail recursive function, you need to 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 recursive tail function that will be perfectly optimized by the compiler. Enjoy it!