The result of raising one number to a positive integer power

The result of raising one number to a positive integer power can also be calculate recursively based on the equation

* when y is even

*when y is odd

Write recursive function That calcuates The power using this equation.

then give the recurrence relation for number of multiplications and divisions that are done by your function.

thank U

Solution

int Power(int x,int y)

{

if(y==0) return 1; //basecase

if(X==0) return x; //basecase

else if(y%2==0) //to check if y is an even number or nor

{

pow(x,y) = pow(x,y/2) * pow(x/y2);

}

else

             return x * pow(x,y/2) * pow(x,y/2)

}

The number of multiplications will be equal to y multiplications + 1 divison to check that it is divisible by 2 or not in order to check it if it is even or not.

We can reduce it by storing the value of pow(x,y/2) in some value and using that value to calculate the remaining funtion

use mid = pow(x,y/2)

if(y%2==0)

return mid * mid;

else

return x * mid * mid;