Java Reference
In-Depth Information
7.16
Starting with
array[first]
.
An iterative solution would certainly start at the first element,
array[first]
, so it is natural to have our first recursive method begin there also. If I ask you to
display the array, you could display
array[first]
and then ask a friend to display the rest of the
array. Displaying the rest of the array is a smaller problem than displaying the entire array. You
wouldn't have to ask a friend for help if you had to display only one element—that is, if
first
and
last
were equal. This is the base case. Thus, we could write the method
displayArray
as follows:
public static void
displayArray(
int
array[],
int
first,
int
last)
{
System.out.print(array[first] + " ");
if
(first < last)
displayArray(array, first + 1, last);
}
// end displayArray
For simplicity, we assume that the integers will fit on one line. Notice that the client would follow a
call to
displayArray
with
System.out.println()
to get to the next line.
7.17
Starting with
array[last]
.
Strange as it might seem, we can begin with the last element in the
array and still display the array from its beginning. Rather than displaying the last element right
away, you would ask a friend to display the rest of the array. After the elements
array[first]
through
array[last
-
1]
had been displayed, you would display
array[last]
. The resulting out-
put would be the same as in the previous segment.
The method that implements this plan follows:
public static void
displayArray(
int
array[],
int
first,
int
last)
{
if
(first <= last)
{
displayArray(array, first, last - 1);
System.out.print (array[last] + " ");
}
// end if
}
// end displayArray
7.18
Dividing the array in half.
A common way to process an array recursively divides the array into
two pieces. You then process each of the pieces separately. Since each of these pieces is an array
that is smaller than the original array, each defines the smaller problem necessary for recursion. Our
first two examples also divided the array into two pieces, but one of the pieces contained only one
element. Here we divide the array into two approximately equal pieces. To divide the array, we find
the element at or near the middle of the array. The index of this element is
int
mid = (first + last) / 2;
Figure 7-6 shows two arrays and their middle elements. Suppose that we include
array[mid]
in the left “half ” of the array, as the figure shows. In Part
b
, the two pieces of the array are equal in
length; in Part
a
they are not. This slight difference in length doesn't matter.
FIGURE 7-6
Two arrays with their middle elements within their left halves
(a)
0
1
2
3
4
56
(b)
0
1
2
3
4
5
6
7
