Results 1 to 7 of 7
Thread: rewriting a recursive function
 04192012, 06:10 AM #1Senior Member
 Join Date
 Feb 2012
 Posts
 219
 Rep Power
 4
rewriting a recursive function
Hello, I have to rewrite a recursive function that take a number and raises it to a power. It's sounds simple, but we have to do it in Logn time using X^2n = X^n times X^n. I am having a hard time implementing this. Here is the code for the other power function that I have to modify.
Java Code:public static double pow(double x, int n ) { if(x == 0 && n <= 0) throw new IllegalArgumentException("Wrong inputs"); else if (x == 0) return 0; else if (n == 0) return 1; else if (n > 0) return x * pow(x, n1); else return 1/pow(x,n); }
 04192012, 06:34 AM #2Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,708
 Rep Power
 13
Re: rewriting a recursive function
Java Code:else if (n > 0) return x * pow(x, n1);
I think what you are asked to do is divide n by 2 instead of subtracting one. There is a small complication to deal with if n is odd. But even that shouldn't be too difficult since, in that case, n1 is even.
 04192012, 02:49 PM #3Senior Member
 Join Date
 Apr 2012
 Location
 New York State of Confusion, USA
 Posts
 137
 Blog Entries
 1
 Rep Power
 0
Re: rewriting a recursive function
Here's the deal. The original algorithm will work just fine for solving x^cn where c is some constant such as 2, 3, 21, etc. It will just take longer than if you take advantage of the algebraic rule that x^cn = (x^c)^n. Note that x^cn does NOT equal x^c * x^n
The original algorithm requires (c*n)1 passes to achieve the answer. Taking advantage of factoring the exponents will take (n1)+(c1) passes.
I think I have that correct upon rereading it before posting.
 04192012, 04:27 PM #4Senior Member
 Join Date
 Feb 2012
 Posts
 219
 Rep Power
 4
 04192012, 04:33 PM #5
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,051
 Blog Entries
 7
 Rep Power
 23
Re: rewriting a recursive function
Write down the recurrence relations for the pow operator:
1) x^0 == 1
2) x^1 == x
3) x^n == x^(n/2)*x^(n/2) if n is even
4) x^n == x*x^(n/2)*x^(n/2) if n is odd
cases 1) and 2) are the sentinel cases while case 3) and 4) describe the recursive step.
kind regards,
JosThe only person who got everything done by Friday was Robinson Crusoe.
 04192012, 04:47 PM #6Senior Member
 Join Date
 Feb 2012
 Posts
 219
 Rep Power
 4
 04192012, 05:48 PM #7
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,051
 Blog Entries
 7
 Rep Power
 23
Re: rewriting a recursive function
The only person who got everything done by Friday was Robinson Crusoe.
Similar Threads

Recursive function to iteractive function
By mikeZet in forum New To JavaReplies: 0Last Post: 03132012, 02:42 AM 
Time a recursive function
By überfuzz in forum New To JavaReplies: 1Last Post: 03252011, 09:27 AM 
recursive function
By jayden in forum New To JavaReplies: 11Last Post: 09022010, 03:00 PM 
Help with recursive function in java
By cachi in forum Advanced JavaReplies: 2Last Post: 07312007, 06:51 PM
Bookmarks