Java Reference
In-Depth Information
and so on. Note that every time we use the preceding formula to find the largest element
in a sublist, the length of the sublist in the next call is reduced by one. Eventually, the
sublist is of length 1 , in which case the sublist contains only one element, which, in turn,
is the largest element in the sublist. From this point onward, we backtrack through the
recursive calls. This discussion translates into the following recursive algorithm, which is
presented in pseudocode:
if the size of the list is 1
the largest element in the list is the only element in the list
else
to find the largest element in list[a]...list[b]
a. find the largest element in list[a + 1]...list[b] and call
it max
b. compare list[a] and max
if (list[a] >= max)
the largest element in list[a]...list[b] is list[a]
else
the largest element in list[a]...list[b] is max
This algorithm translates into the following Java method to find the largest element in an
array:
public static int largest( int [] list,
int lowerIndex, int upperIndex)
{
int max;
if (lowerIndex == upperIndex)
//size of the sublist is 1
return list[lowerIndex];
else
{
max = largest(list, lowerIndex + 1, upperIndex);
if (list[lowerIndex] >= max)
return list[lowerIndex];
else
return max;
}
}
Consider the list given in Figure 13-3.
1
3
[0] [1] [2] [3]
list
5
10
12
8
FIGURE 13-3 List with four elements
Search WWH ::




Custom Search