Assignment 3 – Recursion Solutions | Johns Hopkins University CS 605.202

Assignment 3 – Recursion

Write pseudo-code not Java for problems requiring code. You are responsible for the
appropriate level of detail.

Q1 and Q2 are intended to help you get comfortable with recursion by thinking about
something familiar in a recursive manner. Q3 – Q6 are practice in working with non-
trivial recursive functions. Q7 and Q8 deal with the idea of conversion between iteration
and recursion.

1. Write a recursive algorithm to compute a+b, where a and b are nonnegative integers.

public int add(int a, int b) {
if (b == 0)
return a;
else
return 1 + add(a, b - 1);
}

2. Let A be an array of integers. Write a recursive algorithm to compute the average of the
elements of the array. Solutions calculating the sum recursively, instead of the average, are worth
fewer points.

public double average(int y[], int i) {
double result;
result = (double)y[i] / (double)y.length;
if (i == 0)
return result;
else
return result + average(y, i-1);
}

3. If an array contains n elements, what is the maximum number of recursive calls made by the
binary search algorithm?
The binary search algorithm recursively searches half of the array.
n = 1: 0 recursive calls
n = 2: 1 recursive call
n = 4: 2 recursive calls
n = 8: 3 recursive calls
n = 16: 4 recursive calls
...
This pattern shows that the maximum number of recursive calls is generally ceiling(lg (n)).
However, for the beginning cases of n = 1 and n = 2, an additional step could be required if
the value is not in the list. Therefore, ceiling(lg(n)) + 1 is also acceptable.

4. The expression m % n yields the remainder of m upon (integer) division by n. Define the
greatest common divisor (GCD) of two integers x and y by:

gcd(x, y) = y if ( y ≤ x and x%y == 0)
gcd(x, y) = gcd(y, x) if (x < y )