Java Reference
In-Depth Information
L
ISTING
20.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
a call is returned. The final result is returned in line 10, which is also the return value from
invoking
factorial(n, 1)
in line 4.
20.25
Identify tail-recursive methods in this chapter.
20.26
Rewrite the
fib
method in Listing 20.2 using tail recursion.
✓
✓
Check
Point
K
EY
T
ERMS
base case 738
direct recursion
recursive helper method
747
741
recursive method
738
indirect recursion
741
stopping condition
738
infinite recursion
741
tail recursion
758
C
HAPTER
S
UMMARY
1.
A
recursive method
is one that directly or indirectly invokes itself. For a recursive
method to terminate, there must be one or more
base cases
.
2.
Recursion
is an alternative form of program control. It is essentially repetition with-
out a loop control. It can be used to specify simple, clear solutions for inherently
recursive problems that would otherwise be difficult to solve.
3.
Sometimes the original method needs to be modified to receive additional parame-
ters in order to be invoked recursively. A
recursive helper method
can be defined for
this purpose.
4.
Recursion bears substantial overhead. Each time the program calls a method, the system
must allocate memory for all of the method's local variables and parameters. This can
consume considerable memory and requires extra time to manage the memory.
5.
A recursive method is said to be
tail recursive
if there are no pending operations to be
performed on return from a recursive call. Some compilers can optimize tail recursion
to reduce stack size.
