Thread: Recursion

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    54

    Recursion

    I'm trying to get my binary tree to print out 10 things per line. I'm having issues though, as when the traversing reaches a leaf, on moving to the next printable node my counter is reset to one more than that node's parent, which isn't what I want. I'm not sure how to correct this?

    Here's the functions I'm using
    Code:
    void BinarySortTree::print_preorder()
    {
    	int n = 0;
    	cout << "Preorder: \n";
        preorder(Root, n);
    	cout << "\n\n";
    }//print_preorder
    Code:
    void BinarySortTree::preorder(tree_node* p, int numprint) {
    	if(p != NULL) {
    		numprint++;
    		cout << numprint;
            cout<< p->data<<" ";
    		preorder(p->left, numprint);
    		preorder(p->right, numprint);
        }//if
    	else return;
    }//preorder
    I've moved numprint around a few places, but am not getting the result I wanted.

    I initially planned on just doing preorder(p->right/left, numprint++) and the first part of the print_preorder having an if statement saying if (numprint % 10 == 0) cout << endl;

    Seemed simple enough, but doesn't work I haven't used recursion a whole lot, can you help?

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    So when the first recursive call to preorder is made, that call and all its sub-calls alter their local copy of the numprint variable. Then after they return you pass the same value that you passed to that recursive call into the second recursive call.

    Two obvious solutions come to mind, both involve changing the function signature in some way.
    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"

  3. #3
    Registered User
    Join Date
    Nov 2008
    Posts
    54
    I tried last night, and it seems to me that you're alluding to using a pointer of sorts, so that I'm incrementing what is at a memory location? I haven't been able to properly implement it though.

  4. #4
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    I wouldn't use a pointer.

    The second preorder's numprint needs to depend on the number of nodes in the first preorder's branch. So I'd make preorder return the number of nodes.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I was thinking more along the lines of reference rather than pointer, but either would work.
    And King Mir has the other solution.
    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. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  3. stack and recursion help needed!
    By LouB in forum C++ Programming
    Replies: 3
    Last Post: 07-01-2002, 02:19 PM
  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