Archived

This topic is now archived and is closed to further replies.

recursive functions

This topic is 5672 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have seen the following code used in tree Initialization many times:
void InitTree(TreeNode* Node)
{
    //Init the node
    InitTree(Node->Children[0]);
    InitTree(Node->Children[1]);
}
 
When I run a program with code like this, it runs fine. To me it would seem that only element 0 of each child would get initialized. When the program gets to InitTree(Node->Children[0]), shouldn''t it go back to the beginning of the function? Then, shouldn''t it reach InitTree(Node->Children[0]), and go back to the beginning again? I don''t understand why InitTree(Node->Children[1]) gets called.

Share this post


Link to post
Share on other sites
There should be a check that Node isn''t NULL.
If Node is NULL then InitTree just returns, rewinding the stack.


void InitTree(TreeNode* Node)
{
if( Node == NULL ) return;
//Init the node
InitTree(Node->Children[0]);
InitTree(Node->Children[1]);
}


That way, if element 0 is NULL, you try to initialise it, fail, and move on to element 1, then (if null), back to the parent

Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]

Share this post


Link to post
Share on other sites
Your code says this:
Init child 0 until a leaf is reached, then return.
InitTree(Node->Children[1]); still doesn''t get called.

Also, what do you mean by "rewinding the stack"?

Share this post


Link to post
Share on other sites
When you call a function, the stacks is loaded with the return point (the stack is a zone in memory where the applications store parameters to pass to functions, and the return point).

This means that no matter where you call a function, when it ends, it will return to the next line of code from where the function was called:

main ()
{
function1 ();
function2 ();
}

When function 1 ends, function 2 is called. So, when you are calling a function recursively, the same happens:

int factorial (int a)
{
if (factorial==0) { return 1; }
else { return (a*factorial(a-1)); }
}

Look here:

If you call factorial (0), the function returns a 1, its ok.
If you call factorial (1), the function does 1* factorial (0)...

The second call to factorial(0) is independent, it does what it has to do (return 0) and then you are back in the first call, so you multiply 1 (the number) by 1 (factorial(0)).

You ALWAYS have to put an "return condition" in every recursive functino because if not, you are lost in an infinite loop, that''s why there must be a point where the function ends (this means, not calling itself again).

Note: this factorial works based in that
n! = n * (n-1)!

(in fact, is a definition of factorial based in factorial: recursivity).

In your example, you init a node, then init its first son, then its second son... you don''t have to worry about if a son will have more sons or not because each one will be treated as the root node of that subtree. Recursive magic.

If you want to hear about the stack, ask.

Hope it helps.

Real programers are not afraid from maths!
(from an Asfixia Member I think)
JJpRiVaTe (Private Zone)

Share this post


Link to post
Share on other sites
Okay, I understand it now. Thanx. What a coincidence, I am dealing with factorials in my math class right now!
I had some tree stuff that I was doing in a really complicated way. This makes life simpler.

Proceeding on a brutal rampage is the obvious choice.

[edited by - amish1234 on June 3, 2002 9:50:39 PM]

Share this post


Link to post
Share on other sites
Believe it or not, a lot of instructors don''t even mention the stack when teaching recursion. They teach the logic of recursion without going into any implementation details (the stack). Under these conditions, it''s not surprising that some have difficulty getting it perfect the first time. Recursion took me a good couple of months to really "get" back in high school, and I still try to improve my technique (just whip up a new variant of the Towers of Hanoi problem and try to solve it in optimal time. . . .).

---
blahpers

Share this post


Link to post
Share on other sites
You''re better off checking to see if you should make the recursive call before making it and then calling it if it is ok rather than actually making the recursive call and seeing if you shouldn''t have and returning prematurely if you shouldn''t have.

Share this post


Link to post
Share on other sites
quote:
Original post by bishop_pass
You''re better off checking to see if you should make the recursive call before making it and then calling it if it is ok rather than actually making the recursive call and seeing if you shouldn''t have and returning prematurely if you shouldn''t have.


You are right. But I think it''s easier to understand in the other way (what I have to do, what no). Also, will not matter if he calls the function with a null pointer.

In programmin foundaments they teach it that way, and the next year the other.

Real programers are not afraid from maths! (I am)
(from an Asfixia Member I think)
JJpRiVaTe (Private Zone)

Share this post


Link to post
Share on other sites