Java Reference
In-Depth Information
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.
18.30
✓
✓
Identify tail-recursive methods in this chapter.
Check
18.31
Point
Rewrite the
fib
method in Listing 18.2 using tail recursion.
K
EY
T
ERMS
base case 706
direct recursion
recursive helper method
715
709
recursive method
706
indirect recursion
709
stopping condition
706
infinite recursion
709
tail recursion
727
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 without
a loop control. It can be used to write 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 parameters
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.
Q
UIZ
P
ROGRAMMING
E
XERCISES
Sections 18.2-18.3
*18.1
(
Factorial
) Using the
BigInteger
class introduced in Section 10.9, you can
find the factorial for a large number (e.g.,
100!
). Implement the
factorial
method using recursion. Write a program that prompts the user to enter an inte-
ger and displays its factorial.
*18.2
(
Fibonacci numbers
) Rewrite the
fib
method in Listing 18.2 using iterations.
Hint
: To compute
fib(n)
without recursion, you need to obtain
fib(n - 2)
and
fib(n - 1)
first. Let
f0
and
f1
denote the two previous Fibonacci
Search WWH ::
Custom Search