Results 1 to 7 of 7
Thread: rewriting a recursive function
 04192012, 07:10 AM #1Senior Member
 Join Date
 Feb 2012
 Posts
 219
 Rep Power
 7
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, 07:34 AM #2Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,715
 Rep Power
 16
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, 03: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, 05:27 PM #4Senior Member
 Join Date
 Feb 2012
 Posts
 219
 Rep Power
 7
 04192012, 05:33 PM #5
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,421
 Blog Entries
 7
 Rep Power
 26
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,
JosBuild a wall around Donald Trump; I'll pay for it.
 04192012, 05:47 PM #6Senior Member
 Join Date
 Feb 2012
 Posts
 219
 Rep Power
 7
 04192012, 06:48 PM #7
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,421
 Blog Entries
 7
 Rep Power
 26
Re: rewriting a recursive function
Build a wall around Donald Trump; I'll pay for it.
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, 04:00 PM 
Help with recursive function in java
By cachi in forum Advanced JavaReplies: 2Last Post: 07312007, 07:51 PM
Bookmarks