Recursion - Multimedia Introduction to Programming Using Java - page 407

For certain recursive calls, called tail-recursive calls, no frame need be allo-
cated, as we discuss in the next subsection. However, your Java compiler does
not use this efficient implementation of tail-recursive calls. In subsection 15.3.2,
we show how you can rewrite tail-recursive calls to make them more efficient.

15.3.1 Tail-recursive procedure calls

We use the first recursive procedure we looked at to discuss tail recursion:

Activity
15-2.2

/** Set elements of b[h..k] to 0 */
public static void setToZero( int [] b, int k, int n) {
if (h > k)
{ return k; }
b[h]= 0;
setToZero(b, h + 1, k);

}
A recursive call of a procedure is tail recursive if it is the last statement in
the procedure body or if it is followed directly by a return statement. In this pro-
cedure, the call:

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

setToZero(b, h + 1, k);
is tail recursive, since it is the last statement in the body.
Because no statements follow this call, it can be executed without using an
additional frame. We illustrate how this can be done using the call:

setToZero(b, 0, 2);
This call creates a frame at the top of the call stack, which looks like this (we
show also the array whose name is in b):

setToZero: 1 ?

h k
5 6 3

b a1 0 2

h k

a1

Execution of the body of setToZero begins. The value of condition h>k is
false , so the statement following the if-statement is executed next. Since h is 0 ,
this statement sets the first array element to 0 , yielding this state:

setToZero: 4 ?

h k
0 6 3

b a1 h 0 k 2

a1

The program counter is now 4 , indicating that the next statement to execute
is the tail-recursive call setToZero(b, h + 1, k); . Once this call is finished, the
above frame becomes active, but its contents will not be referenced because there