Solved
Help with divide and conquer recursion
Posted on 2008-02-11
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.