Java Reference
In-Depth Information
Examples 13-1 through 13-3 illustrate how recursive algorithms are developed and
implemented in Java using recursive methods.
EXAMPLE 13-1 LARGEST ELEMENT IN THE ARRAY
In Chapter 9, we used a loop to find the largest element in an array. This example uses a
recursive algorithm to find the largest element in an array. Consider the list given in
Figure 13-2.
[0] [1] [2] [3] [4]
[5] [6]
list
5
8
2
10
9
4
FIGURE 13-2
List with six elements
The largest element in the list given in Figure 13-2 is
10
.
Suppose
list
is the name of the array containing the list elements. Also suppose that
list[a]...list[b]
stands for the array elements
list[a]
,
list[a + 1]
,
...
,
list[b]
. For example,
list[0]...list[5]
represents the array elements
list[0]
,
list[1]
,
list[2]
,
list[3]
,
list[4]
, and
list[5]
. Similarly,
list[1]...list[5]
represents the array elements
list[1]
,
list[2]
,
list[3]
,
list[4]
, and
list[5]
.To
write an algorithm to find the largest element in
list
, let's think recursively.
If
list
is of length
1
, then
list
has only one element, which is the largest element.
Suppose the length of
list
is greater than
1
. To find the largest element in
list[a]...list[b]
, we first find the largest element in
list[a + 1]...list[b]
and then compare this largest element with
list[a]
. That is, the largest element in
list[a]...list[b]
is given by:
maximum(list[a], largest(list[a + 1]...list[b]))
Let's apply this formula to find the largest element in the list shown in Figure 13-2. This
list has six elements, given by
list[0]...list[5]
. Now the largest element in
list
is:
maximum(list[0], largest(list[1]...list[5]))
That is, the largest element in
list
is the maximum of
list[0]
and the largest element
in
list[1]...list[5]
. To find the largest element in
list[1]...list[5]
, we use
the same formula again because the length of this list is greater than
1
. The largest element
in
list[1]...list[5]
is then:
maximum(list[1], largest(list[2]...list[5]))
Search WWH ::
Custom Search