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