// power.cpp - two recursive implementations of the exponentiation function

#include <iostream>
using namespace std;

// simple recursively implemented exponentiation function (raises x to n'th power);
// run-time: O(n)
double
rpower( double x, unsigned n )
{
   if ( n <= 0 )
      return 1.0;
   
   return x * rpower( x, n-1 );
}


// the following function pair gives a fast recursive exponentiation function);
// run-time: O(log n)
double
aux_frpower( double x, unsigned n, double accum )
{
   // third parameter used as an "accumulator"; this is a 
   // common recursive programming technique
   if ( n <= 0 )
      return accum;
   else if ( n % 2 == 0 )  // n > 0 is even
      return aux_frpower( x*x, n/2, accum );
   else  // n is odd
      return aux_frpower( x, n-1, x*accum );
}

double
frpower( double x, unsigned n )
{
   return aux_frpower( x, n, 1.0 );
}


int
main()
{
   cout << "frpower( 2.0, 1023 ) = " << frpower( 2.0, 1023 ) << endl;
   cout << "rpower( 2.0, 1023 ) = " << rpower( 2.0, 1023 ) << endl;
   
   return 0;
}