Name______________________________________________________________

1. (45%) What output does the following program produce?

#include <iostream.h>

int GV (int x, int y, int n) {

cout << “Enter: “ << x << “, “ << y << endl;

int z = (x + y) / 2;

int returnVal;

if (z * z <= n)

returnVal = z;

else

returnVal = GV (x, y-1, n);

cout << “Leave: “ << x << “, “ << y << endl;

return returnVal;

}

void main () {

cout << GV (1, 7, 7) << endl;

}

Enter: 1, 7

Enter: 1, 6

Enter: 1, 5

Enter: 1, 4

Leave: 1, 4

Leave: 1, 5

Leave: 1, 6

Leave: 1, 7

2

2. (45%) Suppose that a population of bacteria triples every hour. Initially, the population contains two bacteria. After one hour, there are six bacteria in the population and, after two hours, 18 bacteria. Write a recursive function named ComputeNumBacteria that computes the number of bacteria in the population after hour h (where h is an integer greater than or equal to zero).

int ComputeNumBacteria (int h) {

if (h == 0) return 1;

else return 3 * (ComputeNumBacteria (h – 1));

}

3. (10%) Recursive solutions can be awfully inefficient. Give two reasons why, providing examples if necessary.

Recursive solutions, especially those that make multiple recursive calls in their recursive step, make a lot of function calls (which are expensive operations) to do repetitive work. Also, recursions that make multiple recursive calls in their recursive step often do redundant computations. Various examples accepted.