Java Reference
In-Depth Information
/** = k * n! (assuming n>=0 ) */
public static int fact1( int k, int n) {
if (n <= 1) {
return k;
}
return fact1(k * n, n - 1);
}
Applying the first step of the transformation results in this function:
/** = k * n! (assuming n>=0 ) */
public static int fact1( int k, int n) {
tailRecursionLoop: while ( true ) {
if (n <= 1)
{ return k; }
return fact1(k * n, n - 1);
} // end tailRecursionLoop
}
Applying the second step of the transformation results in the function below.
Each time you perform this transformation on a function, use the same label for
the additional loop and the same comment at the end of the loop. Also, include
the statement-comment for each recursive call. These conventions will help you
and others realize that this transformation was applied to the function.
/** = k * n! (assuming n>=0 ) */
public static int fact1( int k, int n) {
tailRecursionLoop: while ( true ) {
if (n <= 1)
{ return k; }
// return fact1(k * n, n - 1);
k= k * n; n= n - 1;
continue tailRecursionLoop;
} // end tailRecursionLoop
}
15.4
Quicksort
Procedure quicksort sorts array segment b[h..k] . Quicksort is the most
famous and most used sorting algorithm. In the worst case, for a segment of n
elements, it takes time proportional to n 2 , but in the average or expected case, it
takes time proportional to n log n . Moreover, it can be engineered to take space
proportional only to log n .
See lesson page
15.4 to get
Quicksort from
the CD.
Search WWH ::

Custom Search