Help with understanding some code
I wrote this code from an algorithm given in a book on data structures.Its for computing powers using recursion, the code works fine, I am just not quite sure what is happening when there is a recursive call to power1 and how it works out the value y. I am pretty sure I am just having a mental block, but have been staring at it for the last hour and am not getting anywhere with it .
publicstaticint power1(int x,int n)
{
int y ;
if (n == 0)
{
return 1;
}
if (isEven(n) ==false)
{
y = power1(x,(n-1)/2);//what's happening in this statement
return x*y*y;
}
else
{
y = power1(x,n/2);//and what is happening here
return y * y;
}
}
Thanks in advance for any assitance anyone can give
Message was edited by:
mdrayne1
[1552 byte] By [
mdrayne1a] at [2007-10-3 12:02:50]
This recursive method is based on 'divide and conquer'. Suppose you
have to raise a number to the power 10. You ask your friend to raise
that number to the power five. After you get the results back you simply
multiply the result by itself.
Now suppose you have to raise a number to the power 5. You ask your
friend again to raise that number to the power 2 (5/2 truncated equals 2).
After you get the results back you multiply the result by itself and you
multiply that by the original number.
Of course raising a number to the power zero equals one.
Now suppose you can't ask your friend to do the job, so you ask yourself
to do that (smaller) job. Basically all you do is this (using power 10 as an
example):
1) n^10 == n^5*n^5
2) n^5 = n^2*n^2*n
3) n^2= n*n
4) n^1 = n*1
kind regards,
Jos
JosAHa at 2007-7-15 14:39:41 >
> Wow thanks again josah , I wish my data Structures
> text book was as clear.
You're welcome of course; thinking 'recursively' is easy as soon as you
understand that little twist of letting 'someone else' do the hard job for
a smaller problem instantiation while you yourself take care of the
trivial parts. Once you've found that solution, substite the method name
for both yourself and that someone else and voila.
kind regards,
Jos
JosAHa at 2007-7-15 14:39:41 >
