Java Reference
In-Depth Information
p1
Draw the Sierpinski triangle
displayTriangles(g, order, p1, p2, p3)
p2
p3
(a)
Recursively draw the small Sierpinski triangle
displayTriangles(g,
order - 1, p1, p12, p31)
p1
p12
p31
Recursively draw the small
Sierpinski triangle
displayTriangles(g,
order - 1, p12, p2, p23)
Recursively draw the
small Sierpinski triangle
displayTriangles(g,
order - 1, p31, p23, p3)
p2
p3
p23
(b)
F
IGURE
20.10
Drawing a Sierpinski triangle spawns calls to draw three small Sierpinski triangles recursively.
Recursion is an alternative form of program control. It is essentially repetition
without a loop.
Key
Point
When you use loops, you specify a loop body. The repetition of the loop body is controlled by
the loop control structure. In recursion, the method itself is called repeatedly. A selection
statement must be used to control whether to call the method recursively or not.
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 con-
sume considerable memory and requires extra time to manage the memory.
Any problem that can be solved recursively can be solved nonrecursively with iterations.
Recursion has some negative aspects: it uses up too much time and too much memory. Why,
then, should you use it? In some cases, using recursion enables you to specify a clear, simple
solution for an inherently recursive problem that would otherwise be difficult to obtain.
Examples are the directory-size problem, the Towers of Hanoi problem, and the fractal prob-
lem, which are rather difficult to solve without using recursion.
The decision whether to use recursion or iteration should be based on the nature of,
and your understanding of, the problem you are trying to solve. The rule of thumb is to
use whichever approach can best develop an intuitive solution that naturally mirrors the
problem. If an iterative solution is obvious, use it. It will generally be more efficient than
the recursive option.
recursion overhead
recursion advantages
recursion or iteration?
Note
Recursive programs can run out of memory, causing a
StackOverflowError
.
StackOverflowError
