programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Recursion Explanation

Jose Campana
Ranch Hand
Posts: 339
Greetings Guys!

This may be a little simple for many programmers here, but believe it or not, I'm having trouble understanding how this recursive "power of" algorithm works. Here it is, please have a look:

What I don't understand is, how can the value of b remain the same in every single iteration ? - This makes it really hard to understand what happens when the method stack begins to pop all the method calls, more specifically, I can't see what b is multiplied against to at this point.

Best Regards,

Luigi Plinge
Ranch Hand
Posts: 441
In your example, b is the base of the exponent, so it has to remain the same. It's the result coming from powerOf which changes in each recursion.

By definition, power-of is b * (b * (b * (b *(...(1)))). The bit inside the brackets is what's returned by the method each time. Any clearer?

You could also stick a statement before the return statements so you can see what's being returned e.g.

Jesper de Jong
Java Cowboy
Sheriff
Posts: 16060
88
• 1

1. In line 4, you call powerOf(4, 3). We go to line 7.
2. The powerOf() method is called with b = 4 and e = 3.

3. The "if" in line 8 is false, so we go to line 11.
4. Now we call: b * powerOf(b, e-1). Filling in the values of the variables, that is: 4 * powerOf(4, 2).
5. There's a recursive call; we go into a nested invocation of the powerOf() method, to line 7. Now the method is called with b = 4 and e = 2. Note that these variables b and e are actually different variables than the one the method was called with in step 2. Each time you call a method, a separate set of the argument variables is created.

6. The "if" in line 8 is false, so we go to line 11.
7. Line 11: we call b * powerOf(b, e-1), which is: 4 * powerOf(4, 1).
8. Again a recursive call. The method is called with b = 4 and e = 1.

9. The "if" in line 8 is false, so we go to line 11.
10. Line 11: we call b * powerOf(b, e-1), which is: 4 * powerOf(4, 0).
11. Again a recursive call. The method is called with b = 4 and e = 0.

12. The "if" in line 8 is true, so we return 1 in line 9.

13. Now the method returns, we go up one stack frame, to the point we went in in step 11.
14. Remember step 10. We now evaluated power(4, 0) = 1, so the result is now 4 * 1 = 4.

15. We return and go up a stack frame again, to the point we went in in step 8.
16. Remember step 7. We now evaluated power(4, 1) = 4, so the result is now 4 * 4 = 16.

17. We return and go up a stack frame again, to the point we went in in step 5.
18. Remember step 4. We now evaluated power(4, 2) = 16, so the result is now 4 * 16 = 64.

19. We return and go up a stack frame again, to the point we went in in step 2.
20. We are now back in the main() method with the answer, 64, which is passed to println().

Jose Campana
Ranch Hand
Posts: 339
Hello guys,

I finally got it, although I had to do some test runs on paper instead of using a debugger. I previously wasn't able to see that each call has to wait for the result of the next one in order to multiply it by the base. And it's really beautiful because it is indeed an accurate representation of the mathematical concept. Thank you, especially to you Jesper, your step by step guide opened my eyes finally.

Remembering recursion has been great !

Have a nice day !

Jose

 Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters?