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