Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

KBab

[java] A power function using recursion.

This topic is 5650 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

For some reason I cannot get my head around recursion. I have this past exam question here and it says write a recursive method to find x^y (both are integers) I have no idea how to do it. This is as far as I''ve got.. public int power(int x, int y) { int result=1; if (y==0) return result; } I have some ideas - like decrementing y (y--) then calling power(x, y) again and appending the result of that call to an int called result but I still dont know how to do it. Thanks in advance!

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
What about this for ex. ? ...

public int power(int x,int y)
{
if (y <= 0) return 1;
return x * power(x,y-1);
}

The first statement assures that the function will terminate, and the second one uses recursion to calc x^y....

Share this post


Link to post
Share on other sites
The example provided by Anonymous Poster is the simple way to do recursion, although there is another another way which works a little better. See if you can figure it out

Hint: Remember that (x^10) * (x^10) = x^20

Stu

Share this post


Link to post
Share on other sites
I''ve done something like this before.
Just a hint: You know that during the recursion, the parameter will either be even or odd. This actually changes how you should provide the answer after the recursion ends. See, if you divide 3 by 2, you get a truncated 1. So to get x^3, you need to multiply x^1 by x^2. Whereas, if x is even, you can say that x^4 = x^2 * x^2.

Keeping this in mind, you can create a recursive power method that has less intermediate results than if you just subtract one from the parameter and call the recursive method again like the AP seems to be suggesting.

NOTE: If you do it this way, it is probably a good idea to have 0 and 1 both as base cases.

Over the centuries, mankind has tried many ways of combating the forces of evil...prayer,
fasting, good works and so on. Up until Doom, no one seemed to have thought about the
double-barrel shotgun. Eat leaden death, demon...
-- Terry Pratchett

Share this post


Link to post
Share on other sites
This was also a question on a past exam for me and the professor posted the answer to it on the course website...

I guess we got a freebie when he gave us the following identities to work with:

x^0 == 1 (duh)
x^n == x^(n/2) * x^(n/2) when n is even
x^n == x * x^(n-1) when n is odd

and the code answer given...


public static int power(int x, int n) {
if(n<0) throw new IllegalArgumentException();
if(n==0) return 1;
if(n%2==0)
return power(x,n/2) * power(x,n/2);
return x*power(x,n-1);
}

edit: stupid mental shortcuts... 2*x != x*x ...

If you work it out, all this does is divide the power into x*x*x*x*...*x.


edit: I'd have posted a URL, but you have to have an account here to view it... but just in case:
http://www.cse.buffalo.edu/~shapiro/UB/CSE116/midtermans.ps

There's also a .pdf, but it seems to be corrupt.

edit: with re: negative exponents, i think the question assumed that n would be at least 0. I think.

[edited by - TSwitch on April 1, 2003 6:41:01 AM]

[edited by - TSwitch on April 4, 2003 4:48:24 PM]

Share this post


Link to post
Share on other sites
KBab: You make less recursive calls to the method, and calling a method takes a certain amount of overhead. For example 2^100, using the ''simple'' algorithm takes 100 calls to the power method, using the ''smart'' one, it takes only 8. That is a lot less calls!

Stu

Share this post


Link to post
Share on other sites
I was writing my recursive power method within a Fraction class so I was able to support negative powers by reversing the numerator and denominator fields of "this" and recalling the power method on the absolute value of the exponent argument.

EDIT: Any ideas as to how this would be done if the exponent were a real number?

EDIT 2: How is x^n = 2 * x^(n/2) for n even?!

[edited by - Kentaro on March 30, 2003 10:16:19 PM]

[edited by - Kentaro on March 30, 2003 10:23:02 PM]

Share this post


Link to post
Share on other sites
If the question posed said that the arguments are integers, you must also account for negative exponents.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Wait a minute... you said this was on the Java AP test?

What possible use would there be for writing your own power function?

*is confused*

Math.pow(double, double); // *sigh*

Seems like a sad crossover from the C++ AP Test. Those losers.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!