# Thread: rewriting a recursive function

1. Senior Member Join Date
Feb 2012
Posts
219
Rep Power
9

## 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, 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.  Reply With Quote

2. Moderator   Join Date
Feb 2009
Location
New Zealand
Posts
4,716
Rep Power
18

## Re: rewriting a recursive function

Java 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.  Reply With Quote

3. Senior 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 (n-1)+(c-1) passes.

I think I have that correct upon re-reading it before posting.  Reply With Quote

4. Senior Member Join Date
Feb 2012
Posts
219
Rep Power
9

## Re: rewriting a recursive function Originally Posted by pbrockway2 Java 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?  Reply With Quote

5. ## 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  Reply With Quote

6. Senior Member Join Date
Feb 2012
Posts
219
Rep Power
9

## Re: rewriting a recursive function Originally Posted by JosAH 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.  Reply With Quote

7. ## Re: rewriting a recursive function Originally Posted by Wnt2bsleepin 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  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•