Power Function through Recursive

neo_2010 · 10-28-2009, 07:57 PM

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.

nadroj · 10-28-2009, 08:45 PM

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.

10-28-2009, 07:57 PM	#1
neo_2010 Registered User Join Date: Oct 2009 Posts: 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 halfhalf ) 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.
neo_2010 is offline

10-28-2009, 08:45 PM	#2
nadroj Registered User Join Date: Oct 2006 Location: Canada Posts: 1,230	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.*
nadroj is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Recursive function	WatchTower	C Programming	11	07-15-2009 07:42 AM
Getting an error with OpenGL: collect2: ld returned 1 exit status	Lorgon Jortle	C++ Programming	6	05-08-2009 08:18 PM
doubt in c parser coding	akshara.sinha	C Programming	4	12-23-2007 01:49 PM
Including lib in a lib	bibiteinfo	C++ Programming	0	02-07-2006 02:28 PM
Problem with Visual C++ Object-Oriented Programming Book.	GameGenie	C++ Programming	9	08-29-2005 11:21 PM