[potator]

So in the needed tutorial section I saw a couple of requests for recursion. Here's my take.

Recursive methods are essentially methods that call themselves. They require powerful logic skills to comprehend and implement. Lets take the implementation for the Math.power function. We could write it like this:

public static int power(int base, int power){
	 if(power == 0)
		  return 1;
	 else{
		  int answer = 1;  int count = 1;
		  while(count <= power){
			   answer *= base;
			   count++;
		  }
		  return answer;
	 }
}

This accomplishes the task, but uses a loop. The same code implemented recursively is:

public static int power(int base, int power){
	 if (power == 0) 
		  return 1;
	 else
		  return base * power(base, power-1);
}

As you can see, the latter solution is shortened and, I think, much more elegant. The concept, though, is hard to understand. First, we need to start with a base case, or case where no recursion takes place. In this example, it is power == 0. If we didn't have a base case, the recursion would go on indefinitely. Second, our recursion loop needs to make progress toward the base case or nothing will happen. In this example it is power(base, power-1). Here is a breakdown of what is happening.

Lets take the case of 2 to power of 4. We know the answer is 16, but how does recursion get this.

1) we call power(2,4)
2) power(2,4) calls power(2,3)
3) power(2,3) calls power(2,2)
4) power(2,2) calls power(2,1)
5) power(2,1) calls power(2,0)
6) power(2,0) returns 1
7) power(2,1) returns (2 * 1) or 2
8) power(2,2) returns (2 * 2) or 4
9) power(2,3) returns (2 * 4) or 8
10) power(2,4) returns (2 * 8) or 16

As you can see, power starts at it's highest value and works toward power==0. When it does reach power==0, the recursion moves backward towards the original method call (power(2,4)) a spits out a value. To simply put it, the method expresses 2^4 as 2*2*2*2. The recursion is basically adding another "*2" to the end. This is, in a nutshell, how recursion works.

[warrenbbs]

Great post - I've been struggling with the concept! However, what I still don't get is once power gets to 0 and it returns 1, why does it then continue and increment power, and how then does it "know" where to stop and spit out the answer?

I though the "return 1;" line would exit the function..?

Thanks for any help!
Warren

[potator]

warrenbbs:

Your question can be explained by tracing the return statements backwards. True, in normal methods, the return statement returns a value to another class, but recursive methods return values to themselves. So in the power(2,4) example, the steps numbered 6 through 9 are returning values to the power method. Step 6 returns the value of 1 to step 5, not the original call of the method. so the line:

return base * power(base, power-1);

in step 5 is now equal to:

return 2 * 1;

but 2 * 1 is not returned to original call of the method, it is returned to the call in step 4. step 4 now returns 2 * 2. This cycle continues until you get back to the very first call of the method, at which the final value is returned to wherever you originally called the method.

[warrenbbs]

potator:

thanks - that really helped!

[potator]

If you want to see another example of recursion, check out this forum.

[xtarx]

thx for this gr8 tutorial it really helped ! . waiting for more ///