Java Reference
In-Depth Information
Tip
If you are concerned about your program's performance, avoid using recursion, because
it takes more time and consumes more memory than iteration. In general, recursion can
be used to solve the inherent recursive problems such as Towers of Hanoi, recursive
directories, and Sierpinski triangles.
performance concern
✓
✓
20.23
Which of the following statements are true?
Check
Point
a. Any recursive method can be converted into a nonrecursive method.
b. Recursive methods take more time and memory to execute than nonrecursive methods.
c. Recursive methods are
always
simpler than nonrecursive methods.
d. There is always a selection statement in a recursive method to check whether a
base case is reached.
20.24
What is a cause for a stack-overflow exception?
A tail recursive method is efficient for reducing stack size.
Key
Point
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 20.11a. However, method
B
in
Figure 20.11b is not tail recursive because there are pending operations after a method call
is returned.
tail recursion
Recursive method A
. . .
. . .
Recursive method B
. . .
. . .
Invoke method B recursively
. . .
. . .
. . .
Invoke method A recursively
(a) Tail recursion
(b) Nontail recursion
F
IGURE
20.11
A tail-recursive method has no pending operations after a recursive call.
For example, the recursive
isPalindrome
method (lines 6-13) in Listing 20.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 20.1 is not tail
recursive, because there is a pending operation, namely multiplication, to be performed on
return from each recursive call.
Tail recursion may be desirable: because the method ends when the last recursive call ends,
there is no need to store the intermediate calls in the stack. Some compilers can optimize tail
recursion to reduce stack size.
A nontail-recursive method can often be converted to a tail-recursive method by using aux-
iliary parameters. These parameters are used to contain the result. The idea is to incorporate
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 20.1 is written in a tail-
recursive way in Listing 20.10.
