Java Reference
In-Depth Information
A tail recursive method is efficient for reducing stack size.
Key
Point
tail recursion
A recursive method is said to be
tail recursive
if there are no pending operations to be per-
formed on return from a recursive call, as illustrated in Figure 18.11a. However, method
B
in
Figure 18.11b is not tail recursive because there are pending operations after a method call is
returned.
Recursive method A
. . .
. . .
Recursive method B
. . .
. . .
Invoke method B recursively
. . .
. . .
. . .
Invoke method A recursively
(a) Tail recursion
(b) Nontail recursion
F
IGURE
18.11
A tail-recursive method has no pending operations after a recursive call.
For example, the recursive
isPalindrome
method (lines 6-13) in Listing 18.4 is tail
recursive because there are no pending operations after recursively invoking
isPalindrome
in line 12. However, the recursive
factorial
method (lines 16-21) in Listing 18.1 is not tail
recursive, because there is a pending operation, namely multiplication, to be performed on
return from each recursive call.
Tail recursion is desirable: because the method ends when the last recursive call ends, there
is no need to store the intermediate calls in the stack. Compilers can optimize tail recursion
to reduce stack size.
A nontail-recursive method can often be converted to a tail-recursive method by using
auxiliary parameters. These parameters are used to contain the result. The idea is to incorpo-
rate the pending operations into the auxiliary parameters in such a way that the recursive call
no longer has a pending operation. You can define a new auxiliary recursive method with the
auxiliary parameters. This method may overload the original method with the same name but
a different signature. For example, the
factorial
method in Listing 18.1 is written in a tail-
recursive way in Listing 18.10.
L
ISTING
18.10
ComputeFactorialTailRecursion.java
1
public class
ComputeFactorialTailRecursion {
2
/** Return the factorial for a specified number */
3
public static long
factorial(
int
n) {
original method
invoke auxiliary method
4
return
factorial(n,
1
);
// Call auxiliary method
5 }
6
7
/** Auxiliary tail-recursive method for factorial */
8
private static long
factorial(
int
n,
int
result) {
auxiliary method
9
if
(n ==
0
)
10
return
result;
11
else
12
return
factorial(n -
1
, n * result);
// Recursive call
recursive call
13 }
14 }
The first
factorial
method (line 3) simply invokes the second auxiliary method (line 4).
The second method contains an auxiliary parameter
result
that stores the result for the fac-
torial of
n
. This method is invoked recursively in line 12. There is no pending operation after
Search WWH ::
Custom Search