?
Solved

Recursion problem...

Posted on 2003-03-17
9
Medium Priority
?
198 Views
Last Modified: 2010-03-31
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
Comment
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
  • Learn & ask questions
9 Comments
 
LVL 35

Expert Comment

by:girionis
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
http://www.nist.gov/dads/HTML/recursion.html
0
 
LVL 9

Expert Comment

by:Ovi
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

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

For multi-threading, this would not be thread safe.
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 9

Expert Comment

by:Ovi
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

by:gen228
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

by:odog1999
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

by:
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

by:gen228
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 also to odog1999, jcaldwel, and girionis for your helpful answers!

Thanks again,
noijet
0
 
LVL 9

Expert Comment

by:Ovi
ID: 8159017
Thanks.
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

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

752 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question