• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Recursion Explanation

 
Ranch Hand
Posts: 339
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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,
 
Ranch Hand
Posts: 441
Scala IntelliJ IDE Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.


 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
reply
    Bookmark Topic Watch Topic
  • New Topic