Thread: recursion

  1. #1
    Registered User
    Join Date
    Dec 2008
    Posts
    10

    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.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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?

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    mirfanud, before anyone else helps you, how about you help yourself by using proper variable names.
    Last edited by iMalc; 03-06-2009 at 02:14 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    I guess ++ could mean "follow the right child", since technically it can mean anything, although to be honest that hadn't occurred to me. But if OP says all he gets is 2 3 5 9, that suggests to me that the left calls are being made and the right calls aren't.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Looking deeper into this, it appears that the way the author has chosen to represent a tree is to store the parent/children relationship in a map. The parent is the .first, and the .second is a list of the children. Finding each nodes children is a simple matter of using .find(). Although the diargam shows a binary tree, the author has not specified that it is merely a binary tree, and the code supports it being an n-ary tree. It's kind of ironic when you consider that a std::map is basically a tree in itself anyway.
    Anyway, this is what actually explains the single recursive call in this case.

    Next time it would help to provide this description up front.
    I do think that this implementation is particularly nasty though. If it is meant to represent a binary tree then there are far better ways of representing it. The iterator 't' should not be a member of the struct. It should instead be a local variable.

    Apart from needlessly calling .find() both before AND after each recursive call, the code itself looks at a glance like it would work.
    Last edited by iMalc; 03-06-2009 at 10:13 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 09:37 AM
  3. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  4. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 09:24 AM
  5. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 02:29 PM