1. Finish and demo the lab that is due today.
2. Because we have not yet had a chance to talk about recursion in lecture, this morning in lab you should read in your text about how a recursive binary search works.
3. Implement a binary search from the code in your book, and test it.

Recursive Problem:  Finding the largest item in an array
Suppose you have an array of integers, and you want to find the largest one using recursion (yes, I know you can do it easily using iteration, but I want you to learn how to design and implement a recursive solution!)

The problem

Assume you have an unsorted array of int from which you want to find the largest item. The pseudo code for the recursive solution you should implement is:

max(int[] anArray)
	if (anArray has only one item)
	   {the item is the maximum }
	else if (anArray has more than one item)
	   { the maximum will be the maximum of two recursive calls:
		    max(left_half_of_anArray) and
		    max(right_half_of_anArray)
	   }

Part 1: The Design

To implement this you will have to consider some of the items we considered when inplementing the recursive binary search in class and some additional ones as well. Briefly these are:
1. How do you pass half an array to each recursive call?
2. What should the base case be? If you don't get it right you will run into infinite recursion, so give it very careful consideration!
3. One difference between this and the binary search is that you must conquer both of the subprograms, not one as binary search does.
4. You must find the maximum of the two maximums returned by the two recursive calls.
I strongly urge you to figure out the solution to these problems before you start to code. It will be more difficult to think in Java than it is in English.

Part 2: The Implementation

This will be a static method. The main method that calls it has been written for you inside a class called max.java. Your max( ) method can be in the same class.

You can write this method in less than 20-30 lines of code (I used 11, not counting comments). Do NOT feel you must get started writing code right away. Much more thought must go into this exercise than typing!!