Recursion

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 (lowIndex and highIndex), and that finds the maximum value in the array, considering only the elements between lowIndex and highIndex, including both ends.

This method should be recursive. If the length of the range is 1, that is, if lowIndex == highIndex, we know immediately that the sole element in the range must be the maximum. So that's the base case.

If there is more than one element in the range, 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.