Power Function through Recursive

This is a discussion on Power Function through Recursive within the C++ Programming forums, part of the General Programming Boards category; Help... I got this code segment from Data Structure Book (Recursive Chapter). I need some one to describe to me ...

  1. #1
    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 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.

  2. #2
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    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 09:50 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21