Computer Science AP Lab 9 - 3/18/03

Partnered lab - hand in on paper

1) Write a recursive function that calculates factorials of integers put in as an argument.  Remember, factorial of 1 is 1.  Also remember that if f(n) is a function that calculates factorials, at any point f(n) = n * f(n-1).  The prototype for your function should look like this:
// precondition: num is >= 1
int factorial(int num);

2) Write a recursive function that calculates the integer square root.  The function will take in three arguments, A) the number you're trying to find the square root of, B) the highest possible value of the square root (which will start off at the value of A) C) the lowest possible value of the square root (which will start off at 1).  The prototype for the function should look like this:
// precondition: num is >= 1, high starts off at num, and low starts off at 1
int squarert(int num, int high, int low);

What you're going to want to do is take "guesses" of where the square root should be by taking the value exactly between high and low and squaring it to see if it's the square root.  If it is, return the value, if not, if it's too high, you want to reset your high value to be the number you just guessed and then you want to try again.  If it's too low, you want the low value to now be the one you just guessed and you want to try again.  The "base" case here will be the situation where you're out of numbers to guess, or high is the same as low.  In that case just return that value.  (it will be the closest integer equivilent of the square root)

3) Write a recursive function that finds the average of an apvector.  It would be wise to keep a counter (starting at the length of the apvector - 1) and before you recurse you should subtract 1 from it.  The prototype for the function would look like this:

// precondition: counter starts at vector.length() - 1
int sumapvector(const apvector<int> vector, int counter);

Keep in mind when counter is < 0, there are no possible values to sum, so you want to return 0.  

Example (non-recursive) code that does the same thing is as follows:

int result;
for (int counter = vector.length() - 1; counter >= 0; counter--) {
    result += vector[counter];
}