• Post Reply Bookmark Topic Watch Topic
  • New Topic

Recursion Explanation  RSS feed

 
Jose Campana
Ranch Hand
Posts: 339
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

Can anybody enlighten me please?

Best Regards,
 
Luigi Plinge
Ranch Hand
Posts: 441
IntelliJ IDE Scala Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android IntelliJ IDE Java Scala Spring
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Just follow in your head what happens when you run the program.

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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!