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!
[java] A power function using recursion.
Author
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!
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!
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....
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....
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
Hint: Remember that (x^10) * (x^10) = x^20
Stu
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
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
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...
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]
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]
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
Stu
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]
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]
If the question posed said that the arguments are integers, you must also account for negative exponents.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
