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
Thanks a lot.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; }
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.
Last edited by nadroj; 10-28-2009 at 08:50 PM.
