# Power Function through Recursive

This is a discussion on Power Function through Recursive within the C++ Programming forums, part of the General Programming Boards category; Help... I got this code segment from Data Structure Book (Recursive Chapter). I need some one to describe to me ...

1. ## Power Function through Recursive

Help...
I got this code segment from Data Structure Book (Recursive Chapter).
I need some one to describe to me the Flow of the function specially ( return half*half ) part.Where is the value of the return

Code:
```#include <iostream.h>

int power(int X,int N)
{
if(N ==	0)
return 1;
else
{
int half = power(X,N/2);

if(N%2 == 0)//even
return half * half ;
else	//odd
return X * half * half ;

}
}

int main()
{
int p = power(3,4);
return 0;
}```
Thanks a lot.

2. for your example, 3^4 = (3^(4/2)) * (3^(4/2)) = (3^2) * (3^2), since N=4 is even.
for an example when N=3 is odd: 3^3 does not equal (3^(3/2)) * (3^(3/2)) = (3^1) * (3^1) = 3^2. note: 3/2 = 1 because your storing it in an integer. so, since N is odd, we have to multiply it again by 3 to get 3^3, so: 3^3 = (3) * (3^1) * (3^1), which is what the algorithm has.

knowing the laws of exponents will help understanding this. that is: (x^a) * (x^b) = x^(a+b). for the first example, 3^4 =(3^2) * (3^2), because 4 = 2 + 2. for the second example, 3^3 does not equal (3^1)*(3^1), because 3 does not equal 1+1. however, 3^3 = (3^1)*(3^1)*(3^1), because 3 = 1+1+1.

EDIT: i realize the algorithm is recursive with base case N = 0, and i only gave one iteration (the first recursive call with N/2). the principle is the same and you could just try to work out the entire trace on paper, continuing what i said above until N = 0.