Looping tail call

This is a discussion on Looping tail call within the C Programming forums, part of the General Programming Boards category; Code: foo( bar ) { ... while( bar ) foo( bar-- ); } It's not quite tail recursive, but can ...

  1. #1
    Registered Abuser
    Join Date
    Jun 2006
    Location
    Toronto
    Posts
    591

    Looping tail call

    Code:
    foo( bar ) {
     ...
     while( bar )
      foo( bar-- );
    }
    It's not quite tail recursive, but can it be converted to a loop?

  2. #2
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Yes, but what you've written is infinite recursion, unless "..." changes the value of bar.

    Write a small test program and enjoy the segfault.

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by @nthony View Post
    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(..._));
    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

  4. #4
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,383
    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.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    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.

  5. #5
    Registered Abuser
    Join Date
    Jun 2006
    Location
    Toronto
    Posts
    591
    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...

  6. #6
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Either I do not understand the nature of your pseudo code or the logic here is seriously flawed:

    Quote Originally Posted by @nthony View Post
    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
    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

  7. #7
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    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?

  8. #8
    Registered Abuser
    Join Date
    Jun 2006
    Location
    Toronto
    Posts
    591
    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
    Last edited by @nthony; 02-08-2010 at 10:17 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How to get RSSI value, send to sensor, sensor receive package, repackage it?
    By techissue2008 in forum Networking/Device Communication
    Replies: 1
    Last Post: 03-04-2009, 09:13 AM
  2. Error C2664 - Trying to call an external Dll
    By jamez05 in forum C++ Programming
    Replies: 3
    Last Post: 08-08-2006, 06:07 AM
  3. Iterative Tree Traversal using a stack
    By BigDaddyDrew in forum C++ Programming
    Replies: 7
    Last Post: 03-10-2003, 04:44 PM
  4. Function call resulting in a strange looping
    By cineplex in forum C++ Programming
    Replies: 4
    Last Post: 02-02-2003, 01:01 PM
  5. call by reference and a call by value
    By IceCold in forum C Programming
    Replies: 4
    Last Post: 09-08-2001, 05:06 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21