• 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

My Recursion

 
Ranch Hand
Posts: 75
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I was doing a recursive assignment for my class, and came up with the following code...



I was told that this is indeed recursive, but there is a better way to do it. I wasn't given any hints or anything, and Im not sure what I need to do to make it better...

Any hints?
 
Rancher
Posts: 280
VI Editor C++ Debian
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Ryan Waggoner:
I was doing a recursive assignment for my class, and came up with the following code...

I was told that this is indeed recursive, but there is a better way to do it. I wasn't given any hints or anything, and Im not sure what I need to do to make it better...

Any hints?



It turns out that there is indeed another way, and it is quite beautiful when you see how it works.

Just a hint to get you started:

If you want say x^7, what you are doing now is
x * x^6, which in turn becomes x * x * x^5 and so on.

Instead, you may note that 7 = 4 + 2 + 1, so that
(x^2)^2 * (x^2) * x would also get you the same result.

hope this helps,
- Anand
 
Sheriff
Posts: 22785
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think you should return the result of each recursive call:

 
Rob Spoor
Sheriff
Posts: 22785
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Anand Hariharan:
It turns out that there is indeed another way, and it is quite beautiful when you see how it works.

Just a hint to get you started:

If you want say x^7, what you are doing now is
x * x^6, which in turn becomes x * x * x^5 and so on.

Instead, you may note that 7 = 4 + 2 + 1, so that
(x^2)^2 * (x^2) * x would also get you the same result.

hope this helps,
- Anand


This is just as efficient as the original method, as in the end you'll still perform x * x * x * x * x * x * x. I don't call that better, just more esotheric
 
Ryan Waggoner
Ranch Hand
Posts: 75
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That's wonderful, thank you both...

Another question if I can...

When a recursive method calls itself... I am having kind of a hard time understanding what is going on, in terms of memory. Every time it calls itself, it runs the method in a different space in memory?
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
[Rob']: This is just as efficient as the original method, as in the end you'll still perform x * x * x * x * x * x * x. I don't call that better, just more esotheric

I don't think that's correct. The original method would require six multiplications to calculate x^7, whereas what Anand suggests would require only four. And x^8 would require only three.
 
Jim Yingst
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
[Ryan]: When a recursive method calls itself... I am having kind of a hard time understanding what is going on, in terms of memory. Every time it calls itself, it runs the method in a different space in memory?

Well, a slightly different space, usually immediately adjacent to where it ws running the last method. The general area in memory where methods are run is called the stack. As a simple model, think of a desk, initially empty. whenever you start a new method, you lay down a new piece of paper to write on. When you finish the method, you remove the paper, and go back to what you were doing on the previous piece of paper. It works the same way whether a method calls a different method, or the same method.
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic