#### Archived

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

# [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.

## 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 on other sites

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 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 on other sites
Thanks AP good stuff.
stustill: don''t see how that way is more efficient?

##### 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 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

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 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 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 on other sites
If the question posed said that the arguments are integers, you must also account for negative exponents.

##### Share on other sites
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.

1. 1
2. 2
Rutin
18
3. 3
4. 4
5. 5
frob
12

• 9
• 23
• 17
• 9
• 17
• ### Forum Statistics

• Total Topics
632610
• Total Posts
3007403

×