# recursion

• 03-06-2009
mirfanud
recursion
Hi,
I have a simple tree and I just want to print the parent id and the child ids using recursion. I have somthing like this.

2
/ \
3 4
/ \ / \
5 6 7 8
/\ /\ /\ /\
9 10 11 12 13 14 15 16

I want to traverse it like this
2 3 5 9 10 6 11 12 4 7 13 14 8 15 16.

I wrote simple recursion. the full program si provided at http://pastebin.ca/1354550. Just to illustrate the recrusion (If u happen to look at code dont messed up with the fill method, I am using this to simply my problem using in my project)

Code:

```        int order_display(long fid, long tid)         {                 fot = FOST.find(fid);                 if(fot != FOST.end())                 {                         int r = 0;                         for(FOT.t = FOT.tids.begin();                                 FOT.t != FOT.tids.end();                                 FOT.t++)                                 {                                         fot1 = FOST1.find(*FOT.t);                                         if(fot1 != FOST1.end())                                         {                                                 cout<<"tid "<<*FOT.t<<", creates family "<<FOT1<<endl;                                                                                         //recursion                                                 order_display(FOT1, *FOT.t);                                         }                                         else                                         {                                                 cout<<"tid == "<<*FOT.t<<endl;                                         }                                 }                                 //return 1;                 }         }```
Can you please identify what is the problem. Coz I go till 2 3 5 8 9. But it does not go to the other family on the next to the lowest level. Any help will be appreciated.

i.
• 03-06-2009
tabstop
I didn't look at your pastebin code, but looking at your tree:
(1) this is a bog standard pre-order traversal
(2) since this is a binary tree, each node should have two children, so you should be making two recursive calls
(3) unless you have a forest of binary trees, why would you want to use a for loop for this?
• 03-06-2009
iMalc
Those last two questions / points are explained by the fact that a tail-recursive call can be translated into iteration (i.e. a loop) instead. When there are two recursive calls, then obviously only at most one of those can be tail-recursive.
Thus you would have one loop and one recursive call. Hence my own in-order tree processing function:
Code:

```template <class TNode> void InorderProcess(TNode *head, void ProcessItem(TNode *item)) {         while (head != NULL) {                 InorderProcess(head->left, ProcessItem);                 ProcessItem(head);                 head = head->right;         } }```
The advantage is that a tree with a huge number of items that has degraded to a list following the right pointers doesn't blow the stack. Of course a list following the left pointers still does. It's also probably faster, assuming the compiler doesn't perform the same optimisation on its own, since it uses less stack space.

The OP's code is difficlut to understand because it contains non-descriptive names like fid, tid, tids, fot, FOT, fot1, FOST, FOST1, and an unused variable r.