It's not quite tail recursive, but can it be converted to a loop?Code:foo( bar ) { ... while( bar ) foo( bar-- ); }
It's not quite tail recursive, but can it be converted to a loop?Code:foo( bar ) { ... while( bar ) foo( bar-- ); }
Yes, but what you've written is infinite recursion, unless "..." changes the value of bar.
Write a small test program and enjoy the segfault.
C programming resources:
GNU C Function and Macro Index -- glibc reference manual
The C Book -- nice online learner guide
Current ISO draft standard
CCAN -- new CPAN like open source library repository
3 (different) GNU debugger tutorials: #1 -- #2 -- #3
cpwiki -- our wiki on sourceforge
As already pointed out, you have an infinite recursion there. The solution to the bug will also make it tail recursive:
Only other thing left to ask is if you realize the implications of the while loop in your recursion.Code:if ( bar ) foo ( --bar );
Originally Posted by brewbuck:
Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.
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:But I think there must be a more efficient way using iteration. My attempt was: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 );
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...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 );
Either I do not understand the nature of your pseudo code or the logic here is seriously flawed:
Now trees is redefined, which means I can't see how that will parallel this:
Then it seems as tho n gets pointlessly reassigned some values (depending on the nature of .addChild() I guess).Code:for each child in t.children addNodeRecursive( tag, child )
???WTF
C programming resources:
GNU C Function and Macro Index -- glibc reference manual
The C Book -- nice online learner guide
Current ISO draft standard
CCAN -- new CPAN like open source library repository
3 (different) GNU debugger tutorials: #1 -- #2 -- #3
cpwiki -- our wiki on sourceforge
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:
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?Code:Node n = root; Tree trees[] = {myTree}; do { Node tag = null; for each t in trees { trees.append( t.children ); ... node.append( tag ); ...
@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
Last edited by @nthony; 02-08-2010 at 11:17 PM.