recursive functions

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 ]

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"?

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)

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]

amish: If you don''t know what the stack has to do with recursion I''d take jjmontes up on his offer.

-Neophyte

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

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.

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)