Solved

# Recursion problem...

Posted on 2003-03-17
Medium Priority
198 Views
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
Question by:gen228
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 35

Expert Comment

ID: 8153223
> 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

LVL 9

Expert Comment

ID: 8153244
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

LVL 1

Expert Comment

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

0

LVL 9

Expert Comment

ID: 8153358
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 Comment

ID: 8154089
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

LVL 1

Expert Comment

ID: 8156988
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

LVL 9

Accepted Solution

Ovi earned 200 total points
ID: 8157174
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 Comment

ID: 8158967
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.

Thanks again,
noijet
0

LVL 9

Expert Comment

ID: 8159017
Thanks.
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
In this post we will learn how to make Android Gesture Tutorial and give different functionality whenever a user Touch or Scroll android screen.
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.
###### Suggested Courses
Course of the Month11 days, 10 hours left to enroll