Recursion - Multimedia Introduction to Programming Using Java - page 408

are no more statements to execute in the method body. Since the contents of this
frame are not used again, this frame can be used to hold the contents of the frame
for the tail-recursive call, so a new frame for the tail-recursive call need not be
created! For tail-recursive calls: a new frame need not be created because they
can use the current active frame.
Execution of a tail-recursive call, then, can proceed as follows:

1. Evaluate the arguments of the call (in this case, b , h+1 , and k ) and store
them in the parameters of the active frame (variables b , h , and k ).
2. Set the program counter to 1 so that the method body will be executed
again.

Here is the frame after these two steps have been completed and just before
the first statement in the method body is to be executed:

setToZero: 1 ?

h k
0 6 3

b a1 1 2

h k

a1

In method setToZero , the only recursive call is tail-recursive, so any call to
setToZero uses only one frame! This method is almost as efficient as a loop that
sets the array elements to zero.

15.3.2 Tail-recursive function calls

Consider a function f( parameters ) {...} . Its body always terminates with a
return statement:

return expression ;
In a function f , a return statement of the form:

return f( arguments );
is called tail recursive . A return statement of any other form is not tail recursive.
When the call f( arguments ) in a tail-recursive return statement is evaluat-
ed, no additional frame is needed. Instead, the active frame —the one for the
function body currently being executed— can be used. This is similar to the way
tail-recursive procedure calls are handled, and we leave details to you.
There are many functional languages , like ML, Lisp, Scheme, and Haskell.
When programming in these languages, the use of the assignment statement is
avoided as much as possible. Instead, one writes almost all code using function
definitions, function calls, and conditional expressions. Since assignments are
rarely used, loops are used even more rarely. People who are fluent in recursion
usually prefer it over loops because programs are easier to write and understand.
All compilers for functional languages recognize tail-recursive calls and
implement them efficiently, using no extra frames for them, as shown in this and