# Help with divide and conquer recursion

Hello, I am looking for sample recursion questions and there is one that involves writing a recursive exponent program in java.  The method takes in two integers. 1 being the base number and the other being the exponent. The method returns an integer.

int exponent(int x, int n)       so  x = 2 and n = 4 would return 16.

The catch is that the recursive method has to be done using divide and conquer. I have attempted the problem below but I am wondering if my code has the complexity of O(log n)?. My thinking for divide and conquer is this:
pow(2, 4)
/                      \
/                          \
pow(2, 2)                      pow(2,2)
/           \                           /         \
pow(2,1)     pow(2,1)      pow(2,1)   pow(2,1)
/                       \                     /                  \
return n     *      return n   *      return n   *      return n

Here is my code:
public static int dcpow(int x, int y)
{

if ( y == 1)
return x;
else
return dcpow(x,y/2) * dcpow(x,y/2);
}

Is this how you would use divide and conquer on this problem?
Is my code O(log n) and could someone throughly help me understand why it is?

Also, I have been trying to do Fibonacci recursively using divide and conquer. Can someone help me code this problem?

Thank you.
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
>>           return dcpow(x,y/2) * dcpow(x,y/2);

Be careful. This will only work if y is a multiple of 2 (even). If y is odd, then you have to split it up in two unequal parts. Something like :

int split = y / 2;
return dcpow(x, split) * dcpow(x, y - split);

>> Is this how you would use divide and conquer on this problem?

You could indeed do it that way, yes.
0

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Commented:
if( y==0 ) return 1;
if ( y == 1)
return x;
else
return dcpow(x,y/2) * dcpow(x,(y+1)/2);
0
Commented:
It would be more efficient to do something like
if( y==0 ) return 1;
p = dcpow(x,y/2);
p = p*p;
if( y/2 + y/2 < y ) p=p*x;
return p;
which is O(log n) instead of O(n)
0
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.