Java Reference

In-Depth Information

The root of this tree indicates that the call
Fib(n)
calls
Fib(n-1)
and

Fib(n-2)
. Then,
Fib(n-1)
calls
Fib(n-2)
and
Fib(n-3)
, while
Fib(n-2)
calls

Fib(n-3)
and
Fib(n-4)
. Thus, two calls
Fib(n-2)
are made, and one can see

by drawing the next level that three calls
Fib(n-3)
are made. Moreover, one can

prove that in calculating
F
n
,
F
k-1
calls of the form
Fib(n-k)
are made, for
k=

1
,
2
,
3
,
…
. That is a huge number of calls.

One can write a more efficient recursive function for calculating
F
n
, one that

makes at most
n
recursive calls, by adding more parameters to the function. Here

is a specification for the function:

/** = F
n
, for
n>0
, given
k
in range
1..n, a = F
k
, and b = F
k-1
*/

public static int
Fib(
int
n,
int
k,
int
a,
int
b)

To calculate
F
10
, one would write the call
Fib(10, 1, 1, 0)
. Exercise 8 asks

you to write this function.

Adding parameters to help make a recursive function more efficient is akin

to adding local variables to make a loop more efficient. Some of the exercises ask

you to add more parameters to increase efficiency of recursive functions.

15.2.4

Merge sort

We develop a function that sorts array segment
b[h..k]
:

/**
Sort
b[h..k] */

public static void
mergesort(
int
[] b,
int
h,
int
k)

This development shows a fairly simple use of recursion. However, the algo-

rithm is less efficient than algorithm
quicksort
, which is shown in a later sec-

tion, so it is rarely used in practice. This algorithm is called
mergesort
because

it will make use of a method
merge
, which merges two sorted array segments.

We take as the base case a segment with at most one element, for such a seg-

ment is already sorted, so execution of the procedure can terminate immediately.

We consider the case of a segment with at least two elements. Suppose we

view this segment as split into two separate segments,
b[h..e]
and
b[e + 1..k]
.

These segments are chosen to be as close in size as possible, i.e.
e = (h + k) /

2
. Suppose we sort the first segment and then sort the second segment. Then it

remains to merge these two sorted segments together. A procedure to do this was

developed in activity 8-5.7 of the
ProgramLive
CD, and it is called using

merge(b, h, e, k);
. The completed method is given in Fig. 15.7.

This algorithm requires extra space of size
(h - k) / 2
to hold a copied array

segment during the last step of merging the two sorted segments together.

However, the algorithm is much faster than insertion sort or selection sort. If the

original array segment to be sorted has
n
elements, the algorithm always takes

time proportional to
n log n
. In other words, if the original array segment has
2
m

elements, it takes time proportional to
m*2
m
. In the worst case, insertion sort and

selection sort take time proportional to
2
2m
.

Activity

15-3.3

See lesson page

15.3 to get this

function from

the CD.

Search WWH ::

Custom Search