# Thread: rewriting a recursive function

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

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

2. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
15

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

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.

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

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

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

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

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

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

#### Posting Permissions

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