Recursion - Data Structures and Abstractions with Java - page 166

Once again, the base case is an array of one element. You can display it without help. But if the
array contains more than one element, you divide it into halves. You then ask a friend to display one
half and another friend to display the other half. These two friends, of course, represent two recur-
sive calls in the following method:
public static void displayArray( int array[], int first, int last)
{

if (first == last)
System.out.print(array[first] + " ");
else
{

int mid = (first + last) / 2;
displayArray(array, first, mid);
displayArray(array, mid + 1, last);
} // end if
} // end displayArray

Question 5 In Segment 7.18, suppose that the array's middle element is not in either half of the
array. Instead you can recursively display the left half, display the middle element, and then recursively
display the right half. What is the implementation of displayArray if you make these changes?

Note: When you process an array recursively, you can divide it into two pieces. For exam-
ple, the first or last element could be one piece, and the rest of the array could be the other
piece. Or you could divide the array into halves or in some other way.

Note: Finding an array's midpoint
To compute the index of an array's middle element, we should use the statement
int mid = first + (last - first) / 2;
instead of
int mid = (first + last) / 2;
If we were to search an array of at least 2 30 , or about one billion, elements, the sum of first and
last could exceed the largest possible int value of 2 31 - 1. Thus, the computation first + last
would overflow to a negative integer and result in a negative value for mid . If this negative value of
mid was used as an array index, an ArrayIndexOutOfBoundsException would occur. The compu-
tation first + (last - first)/2 , which is algebraically equivalent to (first + last)/2 ,
avoids this error.

7.19

Displaying a bag. In Chapter 2, we used an array to implement the ADT bag. Suppose that a bag had a
method display to display its contents. Although we could define this method iteratively, we'll use
recursion instead. Since display has no parameters, it must call another method— displayArray —
that has parameters and displays the array of bag entries. The arguments in the call to displayArray
would be zero for the first index and numberOfEntries - 1 for the last index, where numberOfEntries
is a data field of the bag's class. Since the array, bag , of bag entries is a data field of the class that
implements the bag, it need not be a parameter of displayArray . Finally, since display is not a static
method, displayArray is not static.
We can use the approach of any version of displayArray given previously. However, we will display
objects, one per line, instead of integers on one line. Using the technique shown in Segment 7.16, we
revised the methods as follows:
public void display()
{