Recursion Worksheet #2 - Homework #9 - Due Friday March 21, 2003

1) Write recursive functions to return the largest value in an apvector.  One of the functions should be written as a tail-recursive function and should have a prototype of void findlargest(const apvector<int> &vector, int position, int &largest) with a precondition being that position starts off at 0 and largest starts at 0.  The embedded recursion version should have a prototype of int findlargest(const apvector<int> &vector, int position) with a precondition being that position starts off at 0.  In both cases you can assume that the apvector consists completely of positive integer values.  Tip: for the embedded recursion the recursive step may be easier to write if you return the larger value:  the current value or the result of the recursive call...  (and if that seems cryptic right now, just do the best you can with it, hand it in and expect an explanation on Friday)

2) Write an embedded recursive function to return the value of a number at a given position of a number series.  The definition of the series is that the first 3 numbers in the series are 1, and every other number is the result of the sum of 2 * the previous value 1 * the value before that and -1 * the value 2 before.  In math notation it can be defined as f(n) = 2*f(n-1) + f(n-2) - f(n-3).  Note: this problem will be very difficult to write in tail recursive form.

3) Your teacher is cruel and sometimes very very crazy.  He has worked for months, and now come up with a very very weird C++ implementation..  this one does not support any kind of loops!   It does however support recursion.  The cruelty comes into play in that he has some code that he wants to work, but it is written in the form of a for loop in a function.  Your job (whether or not you choose to take it) is to rewrite the following function using no loops of any kind.  The prototype for the function MUST match, though you are very much free to use a helper function.  (the function can be either tail-recursive or embedded recursive)

// returns the sum of all values in an apvector lower than a specified level
int sumlower(const apvector<int> &v, int cutoff) {
    int result = 0;
    for (int counter = 0; counter < v.length(); counter++) {
       if (v[counter] < cutoff)
           result = result + v[counter];
    return result;
}