Recursion - Multimedia Introduction to Programming Using Java - page 409

the previous sections. Thus, the additional overhead and space for recursive calls
is eliminated, and the programs are just about as fast as ones that use loops.
Not all compilers recognize tail recursion and implement it efficiently. For
example, Java, by design, does not. In the next section, we show you how you
can rewrite a recursive procedure to make tail-recursive calls efficient.

15.3.3 Removing tail-recursion: procedures

We give a series of three steps for removing tail-recursive calls in a procedure.
Each step preserves the correctness of the procedure. We illustrate removal of
tail-recursive procedure calls using procedure setToZero :
/** Set elements of b[h..k] to 0 */
public static void setToZero( int [] b, int k, int n) {
if (h > k)
{ return k; }

Activity
15-2.3

b[h]= 0;
setToZero(b, h + 1, k);

}
Here are the first two steps:

Using synched
animation,
activity 15-2.3
explains this
material better.

Step 1. Insert a return statement at the end of the body (if it is not
there).

Step 2. Place the procedure body in a while-loop with loop con-
dition true . Label the while-loop and indicate its end with a com-
ment. Use this convention whenever you implement tail-recursion
efficiently yourself.

Here is the result of applying the first two steps to procedure setToZero :
/** Set elements of b[h..k] to 0 */
public static void setToZero( int [] b, int k, int n) {
tailRecursionLoop: while ( true ) {
if (h > k)
{ return k; }
b[h]= 0;
setToZero(b, h + 1, k);
return ;
} // end tailRecursionLoop

}
Step 2 leaves the procedure correct, for the following reason. Since the last
statement of the loop body is a return statement, the iteration of the loop is guar-
anteed to terminate by executing a return statement, so the old procedure body is
executed exactly once, just as before the loop was added.