Java Reference
In-Depth Information
• Recursion repeatedly invokes the mechanism, and consequently the overhead, of method calls.
• Any problem that can be solved recursively can also be solved iteratively.
• A recursive approach is normally preferred over an iterative approach when it more naturally mir-
rors the problem and results in a program that is easier to understand and debug.
• A recursive approach can often be implemented with few lines of code, but a corresponding it-
erative approach might take a large amount of code. Another reason to choose a recursive solu-
tion is that an iterative solution might not be apparent.
Section 18.9 Fractals
• A fractal (p. 791) is a geometric figure that is generated from a pattern repeated recursively an
infinite number of times.
• Fractals have a self-similar property (p. 791)—subparts are reduced-size copies of the whole.
Section 18.10 Recursive Backtracking
• In recursive backtracking (p. 802), if one set of recursive calls does not result in a solution to the
problem, the program backs up to the previous decision point and makes a different decision,
often resulting in another set of recursive calls.
Self-Review Exercises
18.1
State whether each of the following is
true
or
false
. If
false
, explain why.
a)
A method that calls itself indirectly is not an example of recursion.
b)
Recursion can be efficient in computation because of reduced memory-space usage.
c)
When a recursive method is called to solve a problem, it actually is capable of solving
only the simplest case(s), or base case(s).
d)
To make recursion feasible, the recursion step in a recursive solution must resemble the
original problem, but be a slightly larger version of it.
18.2
A is needed to terminate recursion.
a) recursion step
b)
break
statement
c)
void
return type
d)
base case
18.3
The first call to invoke a recursive method is
.
a)
not recursive
b)
recursive
c)
the recursion step
d)
none of the above
18.4
Each time a fractal's pattern is applied, the fractal is said to be at a new
.
a)
width
b)
height
c)
level
d)
volume
18.5
Iteration and recursion each involve a
.
a)
repetition statement
b)
termination test
c)
counter variable
d)
none of the above
