• Status: Solved
• Priority: Medium
• Security: Public
• Views: 200

# Recursion problem...

Hi, I am having trouble understanding how recursion is working in this example(below).  I see the count being reset to  1, every time countNodes is called again.

static int countNodes( TreeNode root ) {
if ( root == null )
return 0;
else {
int count = 1;
count += countNodes(root.left);
count += countNodes(root.right);
return count;
}
} // end countNodes()

*This example is with the binary tree:
1
/ \
2   3
/ \   \
4   5   6
*If you can tell me a recursion tutorial for beginners, that would be helpful also.

Thanks for any input!
noijet
0
gen228
1 Solution

Commented:
> Hi, I am having trouble understanding how recursion is working in this example(below)

What exactly do you not udnerstand?

Some recursion links that might be of help:

http://personal.vsnl.com/erwin/recursion.htm
http://geminga.it.nuigalway.ie/cai_tutor/recursio.htm
0

Commented:
count = 1 refer to the current node in the recursive method call (the current node is counted also). This will not overwrite the value of the count every time the recursive call is made, since the new declaration and initialization is made in a different method context.
0

Commented:
If you are single-threaded having count as a member of the class, not local to the method will work.

0

Commented:
1
/ \
2   3
/ \   \
4   5   6

If you see the problem in a nonrecursive way should look like:

rootNode = 1
count1 = 1

rootNode = 2
count2 = 1

rootNode = 4
count4 = 1
//4 has no children, so we would not go down any further

count2 += count4 //2

rootNode = 5
count5 = 1
//5 has no children, so we would not go down any further

count 2 += count5 // 3

count1 += count2 //4

rootNode = 3
count3 = 1
//3 has no left children, so we will go down to right only

rootNode = 6
count6 = 1
//6 has no children, so we would not go down any further
count3 += count6 //2

count1 += count3 //6

//counting has finished total count1 = 6 nodes.

I the above pseudocode, there is a variable count<number> specific for each node. E.G. node 3 => count3; node 5 => count5, ...
0

Author Commented:
Thanks for taking the time to explain this Ovi.  I have questions about the *** section *** below right after count4 = 1.
From my understanding at this point when 'count += countNodes(root.left(left of 4))' is actually
'count += countNodes(null) because there is no left child to 4.  But then how does the program get back up to 2?

rootNode = 1
count1 = 1

rootNode = 2
count2 = 1

rootNode = 4
count4 = 1
//4 has no children, so we would not go down any further
*** section ***

Thanks again
noijet
0

Commented:
gen228,

when the method reaches a null pointer, the code does the following:
if ( root == null )
return 0; //count += 0 in previous call

It then moves back up to the previous recursion, and proceeds with
count += countNodes(root.right);

hth,
Odog
0

Commented:
yes, the first if statement in the recursive method ensure it goes back if there are no more children to go to.

static int countNodes( TreeNode root ) {
if ( root == null )
return 0;
else {
int count = 1;
count += countNodes(root.left);
count += countNodes(root.right);
return count;
}
} // end countNodes()

*This example is with the binary tree:
1
/ \
2   3
/ \   \
4   5   6

suppose you are in the recursive method and the current node is 4. The count for node4 is equal to 1. In the next step you have the following statement count += countNodes(root.left). This is a recursive call so in the 'new method countNodes(Node)', the root will be the left node of the node 4. Since this is null, it not exist, the method call will return 0, so count4 remains unmodified. The same thing happens for right node of the node 4. At this point node4 is considered to be done. If you follow this judgement up in the tree, you will see that count2 (for node 2) is calculated in the same principle. First count2 = 1, after that the count2 += countNodes(root.left). This meens first will be calculated the left child of the node 2 which is ... node 4, we have already seen how get's done. The next step is to calculate the right child which is 5, and the calculation will be the sameas in case of node 4.

Basically the method does not know how to return to a parent call, only finishes geting a result of 0 or more. You will see more clearly if you will consider not to use recursive calls, but consecutive calls to methods for each node, like this:

static int countNodes( TreeNode root ) {
//current node is 1
if ( root == null )
return 0;
else {
int count = 1;
count += countNode2(root.left);
count += countNode3(root.right);
return count;
}
} // end countNodes()

static int countNode2( TreeNode root ) {
//current node is 2
if ( root == null )
return 0;
else {
int count = 1;
count += countNode4(root.left);
count += countNode5(root.right);
return count;
}
} // end countNodes()

static int countNode4( TreeNode root ) {
//current node is 4
if ( root == null )
return 0;
else {
int count = 1;
count += countNode4Left(root.left);
count += countNode4Right(root.right);
return count;
}
} // end countNodes()

static int countNodes( TreeNode root ) {
//current node is 5
if ( root == null )
return 0;
else {
int count = 1;
count += countNode5Left(root.left);
count += countNode5Right(root.right);
return count;
}
} // end countNodes()

static int countNode4Left( TreeNode root ) {
//current node is left node of 4 = null
if ( root == null )
//YES is NULL, SO WILL RETURN 0
return 0;
else {
// WILL NEVER ENTER THRU HERE
int count = 1;
count += countNodex(root.left);
count += countNodey(root.right);
return count;
}
} // end countNodes()

static int countNode4Right( TreeNode root ) {
//current node is right node of 4 = null
if ( root == null )
//YES is NULL, SO WILL RETURN 0
return 0;
else {
// WILL NEVER ENTER THRU HERE
int count = 1;
count += countNodex(root.left);
count += countNodey(root.right);
return count;
}
} // end countNodes()

The simulation wil go in the same maneer for the rest of the tree.
0

Author Commented:
Thanks Ovi!  I understand how the recursion works for the binary tree now!  You gave very detailed explainations and alternate ways to look at the code.