# Recursive solution?

• 09-20-2007
Xanz1441
Recursive solution?
I've been tasked to come up with a recursive solution to

X^n = (X^(n/2))^ 2 if n is even

X^n = (X * ((X^(n/2))^2)) if n is odd

now here's the function i've written so far

Code:

```double RecursivePower3(double& baseValue, double expPower, double powerValue){     if (expPower == 0)                 return 1;         if (expPower == 2)                 return baseValue;     if (fmod(expPower, 2) == 0){          //then it's even                 powerValue = pow(pow(baseValue,floor(expPower / 2)), 2);                 return powerValue;     }     else{                 powerValue = (baseValue * pow(pow(baseValue,floor(expPower / 2)), 2);                 return powerValue;     } }```
where baseValue = X and expPower = n and are values entered in by the user.

can anyone tell me how this can be solved recursively?
• 09-20-2007
robatino
You're trying to efficiently compute a nonnegative integer power n of x? Basically just picture the binary representation of n, and which power of x each digit corresponds to. You don't have to do it recursively - there's a fairly simple iterative solution (if you're allowed to use it).
• 09-20-2007
Xanz1441
we're supposed to write a recursive solution implementing that equation i gave at the beginning. The code I gave gives the right answers, it's just not the method wanted.
• 09-20-2007
robatino
Your recursive function should be declared something like
Code:

`double power(double x, unsigned int n)`
(I think that's enough of a hint). You definitely don't want to call pow(), which is expensive. The recursive function doesn't need to do anything more than squaring and/or multiplying.

Edit: If you want, you could extend the function to negative powers by having it call itself if n is negative, and then take the reciprocal.
• 09-20-2007
Xanz1441
I still don't understand where I should call the function inside the function to make it recursive.
• 09-20-2007
matsp
Quote:

Originally Posted by Xanz1441
I still don't understand where I should call the function inside the function to make it recursive.

Yes, a recursive function is calling itself, that is what makes it recursive.

Say for example you have factorial, which is fac(n) = fac(n - 1) * n, and fac(0) = 1, then you have the following code:
Code:

```int fac(int n) {   if (n == 0) return 1;   else       return n * fac(n - 1); }```
You should be able to do the same thing for your function, although it is a little bit more complex.

--
Mats
• 09-20-2007
Xanz1441
so i tried this

Code:

```double RecursivePower3(double& baseValue, double expPower){         if (expPower == 0)                 return 1;         if (expPower == 2)                 return baseValue;     if (fmod(expPower, 2) == 0){          //then it's even                 return (RecursivePower3(baseValue, expPower) / 2);     }         else                 return baseValue * (RecursivePower3(baseValue, expPower) / 2); }```
but it doesn't work.
• 09-20-2007
Daved

X^n = (X^(n/2))^ 2
X^n = (X * ((X^(n/2))^2))

X^n = (X^n) / 2
X^n = X * (X^n) / 2

Also, don't forget that for some value num, num^2 is the same as num*num.
• 09-20-2007
Xanz1441
Ok, now i've got this

Code:

```double RecursivePower3(double& baseValue, double expPower){         double powerValue;         if (expPower == 0)                 return 1;         if (expPower == 2)                 return baseValue;     if (fmod(expPower, 2) == 0){  //then it's even                 return ((RecursivePower3(baseValue, expPower / 2)) * (RecursivePower3(baseValue, expPower / 2)));     }         else                 return (baseValue * ((RecursivePower3(baseValue, expPower / 2)) *(RecursivePower3(baseValue, expPower / 2)))); }```
and for an even numbered expPower, it's outputting the power value of X ^ n/2 only, not squaring it

like for 3 ^ 32 it's outputting 43046721

and for the odd numbers it's not even outputting anything at all
• 09-20-2007
cyph1e
You do realize that (X^(n/2))^2 = X^n and (X * ((X^(n/2))^2)) = X^(n+1)? No need to overcomplicate things. However, if n is an integer, both will be X^n. Are you sure that is not the case? It seems like you should solve this by only using multiplication.

Code:

`X^n = X * X * ... {n times total} ... * X`
(why did I need code-tags to be able to submit this?)

Study matsp's example.

• 09-20-2007
Daved
I think the problem might be your base cases. You have a base case of 2 returning the basevalue. But what that means is that basevalue^2 = basevalue. That of course is not right.

I would think the only base you would need would be 0.

Actually, the other problem I see is that you are using a double for the exponent. Are you sure that should be a double? The formulas look like they use integer math. You might never get to a base case with floating point math because that's not exact and you are using ==.

Change the exponent to an integer and remove the second base case and I think you might have it right.
• 09-20-2007
matsp
Quote:

Originally Posted by cyph1e
You do realize that (X^(n/2))^2 = X^n and (X * ((X^(n/2))^2)) = X^(n+1)? No need to overcomplicate things. However, if n is an integer, both will be X^n. Are you sure that is not the case? It seems like you should solve this by only using multiplication.

Code:

`X^n = X * X * ... {n times total} ... * X`
(why did I need code-tags to be able to submit this?)

Study matsp's example.

Yes, but the solution is supposed to be done slightly differently - by squaring the result of a previous power calculation, you don't need so many steps. If we use the "brute force method"
Code:

```double power(double x, int n) {   if (n == 0) return 1.0;   else return d * power(d, n - 1); }```
For 2 ^5, this takes 6 recursions.

If instead, we take the original formula:

x^5 = x * ((x ^ 2) ^ 2), you only half the number of recursions.

--
Mats
• 09-20-2007
matsp
Here's my obfuscated solution:
Code:

`        if(!I)return 1.0;{double l=rp(i,I>>1);return(I&1)?(i*l*l):(l*l);}`
Note that I don't want to give the full solution, so this is just the function body.

--
Mats
• 09-20-2007
robatino
Here's the iterative solution:
Code:

```double power(double x, unsigned int n) {   double xn = 1.;   while (n) {     if (n & 1) xn *= x;     n >>= 1;     x *= x;   }   return xn; }```