The following is the iterative version of the power(base,n) function which calculates the base^n for all n >= 0

unsigned long long power (unsigned int base, unsigned int n){ unsigned long long rc=1; for(int i = 1;i <= n;i++){ rc = rc * base; } return rc; }

Write the recursive version of the above function. How to do it:

1. State the base case; 1 or more values of n where the solution is known
2. Express a solution for base^n in terms of itself but with a smaller exponent
3. Write the function by testing for the base case(s) and returning the appropriate result and an alternative for the recursive case that uses the expression for step 2.

//lab5.cpp

/* write your recursive power function below */

unsigned long long power (unsigned int base, unsigned int n){

}

//lab5tester.cpp

/****************************************************************/ /* */ /* lab 5 tester file */ /* */ /* To compile: g++ lab5.cpp lab5tester.cpp -std=c++0x */ /* */ /* */ /****************************************************************/ #include using namespace std;

unsigned long long power (unsigned int base, unsigned int n);

int main(void){ unsigned long long correctPower[40]= {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888 }; bool hasBug=false;

for(unsigned int i=0;i<40;i++){ unsigned long long rc = power(2,i); if(rc !=correctPower[i]){ cout << "Error: power(2, " << i << ") = " << correctPower[i] << endl; cout << "Your function returned: " << rc << endl;

hasBug=true; } } if(hasBug){ cout << "Your code has a bug. please fix." << endl; return 1; } else{ cout << "Congrats! your code is now working" << endl; return 0; } }