Thread: Looping tail call

Code:

foo( bar ) {
 ...
 while( bar )
  foo( bar-- );
}

It's not quite tail recursive, but can it be converted to a loop?

Yes, but what you've written is infinite recursion, unless "..." changes the value of bar.

Write a small test program and enjoy the segfault.

Originally Posted by @nthony

It's not quite tail recursive, but can it be converted to a loop?

Why "not quite"?

Anyway it'd be safer as a loop

Code:

while (foo(bar(..._));

As already pointed out, you have an infinite recursion there. The solution to the bug will also make it tail recursive:

Code:

if ( bar )
    foo ( --bar );

Only other thing left to ask is if you realize the implications of the while loop in your recursion.

sorry, the while condition should read "--bar"

@MK27, Mario: it's not "quite" recursive due to the last statement not being a recursive call, but in fact an iteration of a recursive call.
"if( bar )" does not iterate, and "while (foo(bar(..._))" doesn't seem to make any sense? (it neglects a large part of what foo does and foo returns void!)

@Mario: here's the rationale - I need to generate XML nodes based on an internal tree representation I have. This can be accomplished easily via recursion:

Code:

void addNodeRecursive( Node n, Tree t )
 if t is leaf
  n.content = t.value;
 else
  Node tag;
  tag.name = t.name;
  for each child in t.children
   addNodeRecursive( tag, child )
  n.addChild( tag );

But I think there must be a more efficient way using iteration. My attempt was:

Code:

Node n = root;
Tree trees[] = {myTree};
do {
 Node tag = null;
 for each t in trees {
  trees = t.children;
  if t is leaf
   n.value = t.value;
  else 
   Node tag;
   tag.name = t.name;
   n.addChild( tag );
 }
 node = tag;
} while( trees.size > 0 );

The above approach almost works, however at the end of each iteration 'node' and 'trees' always points to the last child before iteration ends. Which makes me think I will need to grow a list of children during iteration so that they can be operated on on the next loop. However such a list starts to get similar to a stack, which makes me wonder if I'm just better of using recursion...

Either I do not understand the nature of your pseudo code or the logic here is seriously flawed:

Originally Posted by @nthony

Code:

Node n = root;
Tree trees[] = {myTree};
do {
 Node tag = null;
 for each t in trees {
  trees = t.children;

Now trees is redefined, which means I can't see how that will parallel this:

Code:

  for each child in t.children
   addNodeRecursive( tag, child )

Then it seems as tho n gets pointlessly reassigned some values (depending on the nature of .addChild() I guess).

???WTF

Why do you want to avoid recursion so much? Is the tree really that deep that you have to worry about stack space?

I guess you're looking for a iterative way to iterate a N-ary tree?

I attempt to reassign trees to its children so that each iteration descends. And node is reassigned to be the current parent. It is flawed though, because at the end of each iteration, 'trees' and 'node' only point to the last sibling's children/parent, so all previous siblings get pruned...

This is why I'm thinking to maintain a list of each siblings children:

Code:

Node n = root;
Tree trees[] = {myTree};
do {
 Node tag = null;
 for each t in trees {
  trees.append( t.children );
  ...
   node.append( tag );
  ...

A list of active children and nodes will need to be queued, processed, then dequeued. Which seems to resemble breadth-first visiting. Maybe I'm missing an easier solution, but if it does require queuing the children I think I'm better off with recursion?

@zacs7: yep, I can't guarantee depth or resources-per-depth (average is ~4 lvls) - but the less the better. The answer is also of pedantic interest since I am a CS major