Data Structures, Algorithms, & Applications in Java
Chapter 55, Exercise 2
The recursive call is easily replaced by a
while loop.
This transformation causes the segments to be output in the
reverse order from that output by the recursive code.
The nonrecursive traceback method
is given below. A test program, input, and output appear
in the files RecursiveDPImageCompression3.*.
This version is expected to run slightly faster as we have replaced
the overhead of method calls by the smaller overhead of a
while loop.
/** output the optimal segment boundaries */
public static void traceback(int [] kay, int n)
{
while (n > 0)
{
System.out.println("New segment begins at "
+ (n - kay[n] + 1));
n -= kay[n];
}
}