Recursion - Advanced Topics in Java: Core Concepts in Data Structures - page 150

What if n were 15 ? First, we would work out x 15/2 , that is, x 7 (call this x7 ). We would then multiply x7 by x7 to
give x 14 . Recognizing that n is odd, we would then multiply this value by x to give the required answer. To summarize:
xn = x n/2 .x n/2 , if n is even and
x.x n/2 .x n/2 , if n is odd
We use this as the basis for a recursive power function that calculates x n more efficiently than the previous
function.
public static double power(double x, int n) {
double y;
if (n == 0) return 1.0;
y = power(x, n/2);
y = y * y;
if (n % 2 == 0) return y;
return x * y;
}
As an exercise, trace the execution of the function with n = 5 and n = 6 .
5.7 Merge Sort
Consider, again, the problem of sorting a list of n items in ascending order. We will illustrate our ideas with a list of
integers. In Section 1.9, we saw how to merge two sorted lists by traversing each list once. We now show how to
use recursion and merging to sort a list. Consider the following algorithm:
sort list
sort first half of list
sort second half of list
merge sorted halves into one sorted list
end sort
If we can sort the two halves and then merge them, we will have sorted the list. But how do we sort the halves? We
use the same method! For instance, to “sort first half of list,” we do the following:
sort (first half of list)
sort first half of (first half of list) //one quarter of the original list
sort second half of (first half of list) //one quarter of the original list
merge sorted halves into one sorted list
end sort
And so on. For each piece we have to sort, we break it into halves, sort the halves, and merge them. When do we
stop using this process on a piece? When the piece consists of one element only; there is nothing to do to sort one
element. We can modify our algorithm as follows:
sort a list
if the list contains more than one element then
sort first half of list
sort second half of list
merge sorted halves into one sorted list
end if
end sort