Recursion - Multimedia Introduction to Programming Using Java - page 405

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.