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.

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.

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.

Re: rewriting a recursive function

Quote:

Originally Posted by

**pbrockway2** 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?

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

Re: rewriting a recursive function

Quote:

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.

Re: rewriting a recursive function

Quote:

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