Confusion of Recursion

[islam-morad]

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,

[Ezzaral]

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]

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

[kvass]

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.

[islam-morad]

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]

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]

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: