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
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:

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
• Number of slices to send:
Optional 'thank-you' note:
I think you should return the result of each recursive call:

Rob Spoor
Sheriff
Posts: 22785
131
• Number of slices to send:
Optional 'thank-you' note:

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
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
[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
• Number of slices to send:
Optional 'thank-you' note:
[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.