• Post Reply Bookmark Topic Watch Topic
  • New Topic

My Recursion  RSS feed

 
Ryan Waggoner
Ranch Hand
Posts: 75
  • Mark post as helpful
  • send pies
  • 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?
 
Anand Hariharan
Rancher
Posts: 272
C++ Debian VI Editor
  • Mark post as helpful
  • send pies
  • 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
 
Rob Spoor
Sheriff
Posts: 21135
87
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think you should return the result of each recursive call:

 
Rob Spoor
Sheriff
Posts: 21135
87
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • 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
  • 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?
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • 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
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • 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.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!