# rewriting a recursive function

• 04-19-2012, 06:10 AM
Wnt2bsleepin
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.

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, n-1); else     return 1/pow(x,-n); }```
I am able to follow the recursive calls for this method fine, I just don't know how to implement that weird form I was given to use. Thanks for any help.
• 04-19-2012, 06:34 AM
pbrockway2
Re: rewriting a recursive function
Code:

```else if (n > 0)       return x * pow(x, n-1);```
The idea seems to be that you keep subtracting 1 from n until it becomes small (zero or one).

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, n-1 is even.
• 04-19-2012, 02:49 PM
jlczuk
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 (n-1)+(c-1) passes.

I think I have that correct upon re-reading it before posting.
• 04-19-2012, 04:27 PM
Wnt2bsleepin
Re: rewriting a recursive function
Quote:

Code:

```else if (n > 0)       return x * pow(x, n-1);```
The idea seems to be that you keep subtracting 1 from n until it becomes small (zero or one).

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, n-1 is even.

Would the modification involve adding another base case? Why would it being odd matter?
• 04-19-2012, 04:33 PM
JosAH
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,

Jos
• 04-19-2012, 04:47 PM
Wnt2bsleepin
Re: rewriting a recursive function
Quote:

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,

Jos

Thank you very much. I was able to solve it. Now I just have to write it nonRecursively.
• 04-19-2012, 05:48 PM
JosAH
Re: rewriting a recursive function
Quote:

Thank you very much. I was able to solve it. Now I just have to write it nonRecursively.

Think of the exponent n as a binary number; each bit represents a power of the number x: x^1, x^2, x^3, x^4 etc. If a bit in that number n is 1, multiply your result by the corresponding power of x.

kind regards,

Jos