Recursion

It's like a nightmare that doesn't go away when you wake up. Many of the patterns we have seen for traversing arrays can also be written recursively. It is not common to do so, but it is a useful exercise.

1.

Write a method called maxInRange that takes an array of integers and a range of indices (low and high), and that finds the maximum value in the array, considering only the elements between low and high, including both ends.

This method should be recursive. If the length of the range is 1, that is, if low == high, we know immediately that the sole element in the range must be the maximum. So that's the base case. If the array is bigger than 1, we can break the array into two pieces, find the maximum in each of the pieces, and then find the maximum of each of the piece-maxima.

2.

One you have maxInRange working, you can write a wrapper method called max that works like this

    public static int max (int[] a) {
      return maxInRange (a, 0, a.length-1);
    }

The wrapper method uses the worker method to do the real work. The role of the wrapper is to provide an interface to the outside world that is easier to use.

3.

Write a recursive version of find using the wrapper-worker pattern. find should take an array of integers and a target integer. It should return the index of the first location where the target integer appears in the array, or -1 if it does not appear. find was called grapefruit on the exam.