Confusion of Recursion

Question

islam-morad 0 Newbie Poster

14 Years Ago

Hello guys,

i'm studying the Java programming language. every thins were going very well, but once i have encountered RECURSION i started to feel so bad.

there is a recursive method that is blowing my mind. I can't figure out how does it print that the sum of a set of numbers without using a variable that keeps track of the current value of the sum.

My problem is that i totally understood how recursion is working however, when i try to write a recursive method, i fail.

Here is the method. i wish you could help me understand it.

/**
	 * Return the number of leaves in the tree to which node points.
	 */
	static int countLeaves(TreeNode node) {
		
		if(node == null){
			return 0;
		} else if(node.left == null && node.right == null){
			return 1;
		} else {
			return countLeaves(node.left) + countLeaves(node.right);
		}
	} // end countNodes()

Best regards,

java

3 Contributors
6 Replies
129 Views
22 Hours Discussion Span
Latest Post 14 Years Ago Latest Post by islam-morad

kvass 70 Junior Poster

14 Years Ago

Imagine a simple branch structure:

|
  / \
 |   |
/ \   \

The number of leaves for the top part will be the total number of leaves on the left + the total number of leaves on the right.

On the left there is again a branch, so the number of leaves for this part will be the total number of leaves on its left + the total number of leaves on its right.

On this far left branch, its node.left and node.right are both null. Hence, it will return 1 (case 2 of 3) because it is a dead end (a leaf).

On the right there is nothing (it is null). Hence, it will return 0 (case 1 of 3) because it is nonexistant.

On the left we have now calculated the number of leaves for this part, because 0 + 1 = 1. There is 1 leaf here, so that number is returned upward.

Now we know the number of leaves on the left (1). Time to investigate the number on the right.

On the right there is again a branch, so the number of leaves for this part will be the total number of leaves on its left + the total number of leaves on its right.

On the right's left branch (the one pointing toward the center of the tree in the diagram), its node.left and node.right are both null. Hence, it will return 1 (case 2 of 3) because it is a dead end (a leaf).

On the far right branch, its node.left and node.right are both null. Hence, it will return 1 (case 2 of 3) because it is a dead end (a leaf).

On the right we have now calculated the number of leaves for this part, because 1 + 1 = 2. There are 2 leaves here, so that number is returned upward.

Now we have calculated the number of leaves on the left (1) and the number of leaves on the right (2). 1 + 2 = 3, so 3 is returned.

-----------------------

This is basically how the recursion works. Case 1 is when there is nothing there (returns 0). Case 2 is when there is a leaf (returns 1). Case 3 is when there is a branch, so you have to rerun the check for its left side and its right side and add them.

Typically recursion works like this:

recursiveMethod()
{
   if (base case)
       return [some #]
   else
       call recursiveMethod() again w/ modified parameters.
}

An example of this format is as follows:

public static int power(int base, int exponent)
{
   if (exponent==0) //Bottom case -- no more recursive calls when this is reached.
       return 1;
   else
       return base * power(base,exponent-1);
}

So if this were run on the input (3,3), the computer would evaluate:

power(3,3) = 3 * power(3,2)
power(3,2) = 3 * power(3,1)
power(3,1) = 3 * power(3,0)
power(3,0) = 1 //Base case!!!
power(3,1) = 3 * 1 = 3
power(3,2) = 3 * 3 = 9
power(3,3) = 3 * 9 = 27
27 is returned.

Edited 14 Years Ago by kvass because: n/a

islam-morad commented: Perfect, Thanks +0

Ezzaral commented: Very detailed and helpful. +14

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Ezzaral 2,714 Posting Sage Team Colleague Featured Poster · Answer 1 · 2010-09-30T01:06:24+00:00

If you trace the function values through a small test node, you will see how the sum is automatically updated as the nested calls return back up the call stack.

islam-morad 0 Newbie Poster · Answer 2 · 2010-09-30T01:22:57+00:00

I have tried to trace it using the debugged, but i couldn't. it is very confusing

islam-morad 0 Newbie Poster · Answer 3 · 2010-09-30T01:42:15+00:00

Imagine a simple branch structure:
|
  / \
 |   |
/ \   \
The number of leaves for the top part will be the total number of leaves on the left + the total number of leaves on the right.
On the left there is again a branch, so the number of leaves for this part will be the total number of leaves on its left + the total number of leaves on its right.
On this far left branch, its node.left and node.right are both null. Hence, it will return 1 (case 2 of 3) because it is a dead end (a leaf).
On the right there is nothing (it is null). Hence, it will return 0 (case 1 of 3) because it is nonexistant.
On the left we have now calculated the number of leaves for this part, because 0 + 1 = 1. There is 1 leaf here, so that number is returned upward.
Now we know the number of leaves on the left (1). Time to investigate the number on the right.
On the right there is again a branch, so the number of leaves for this part will be the total number of leaves on its left + the total number of leaves on its right.
On the right's left branch (the one pointing toward the center of the tree in the diagram), its node.left and node.right are both null. Hence, it will return 1 (case 2 of 3) because it is a dead end (a leaf).
On the far right branch, its node.left and node.right are both null. Hence, it will return 1 (case 2 of 3) because it is a dead end (a leaf).
On the right we have now calculated the number of leaves for this part, because 1 + 1 = 2. There are 2 leaves here, so that number is returned upward.
Now we have calculated the number of leaves on the left (1) and the number of leaves on the right (2). 1 + 2 = 3, so 3 is returned.
-----------------------
This is basically how the recursion works. Case 1 is when there is nothing there (returns 0). Case 2 is when there is a leaf (returns 1). Case 3 is when there is a branch, so you have to rerun the check for its left side and its right side and add them.
Typically recursion works like this:
recursiveMethod()
{
   if (base case)
       return [some #]
   else
       call recursiveMethod() again w/ modified parameters.
}
An example of this format is as follows:
public static int power(int base, int exponent)
{
   if (exponent==0) //Bottom case -- no more recursive calls when this is reached.
       return 1;
   else
       return base * power(base,exponent-1);
}
So if this were run on the input (3,3), the computer would evaluate:
power(3,3) = 3 * power(3,2)
power(3,2) = 3 * power(3,1)
power(3,1) = 3 * power(3,0)
power(3,0) = 1 //Base case!!!
power(3,1) = 3 * 1 = 3
power(3,2) = 3 * 3 = 9
power(3,3) = 3 * 9 = 27
27 is returned.

Thanks for answering me. You answer is very clear thanks again.

kvass 70 Junior Poster · Answer 4 · 2010-09-30T09:40:13+00:00

Hmm... I think I misdrew the diagram at the beginning... it should have looked like this:

|
  / \
 |   |
/   / \

But if you understood it then great :P

islam-morad 0 Newbie Poster · Answer 5 · 2010-09-30T16:28:47+00:00

Hmm... I think I misdrew the diagram at the beginning... it should have looked like this:
|
  / \
 |   |
/   / \
But if you understood it then great :P

Actually i noticed that you didn't draw it correctly. so i draw mine. :icon_biggrin: