Java Reference
In-Depth Information
587
Chapter 13 Recursion
C
HAPTER
G
OALS
ȗ
To learn about the method of recursion
ȗ
To understand the relationship between recursion and iteration
ȗ
To analyze problems that are much easier to solve by recursion than by
iteration
ȗ
To learn to Ȓthink recursivelyȓ
ȗ
To be able to use recursive helper methods
ȗ
To understand when the use of recursion affects the efficiency of an algorithm
The method of recursion is a powerful technique to break up complex
computational problems into simpler ones. The term Ȓrecursionȓ refers to the fact
that the same computation recurs, or occurs repeatedly, as the problem is solved.
Recursion is often the most natural way of thinking about a problem, and there are
some computations that are very difficult to perform without recursion. This chapter
shows you simple and complex examples of recursion and teaches you how to Ȓthink
recursivelyȓ.
587
588
13.1 Triangle Numbers
We begin this chapter with a very simple example that demonstrates the power of
thinking recursively. In this example, we will look at triangle shapes such as the ones
from
Section 6.3
. We'd like to compute the area of a triangle of width n, assuming
that each [] square has area 1. This value is sometimes called the n
th
triangle number.
For example, as you can tell from looking at
[]
[][]
[][][]
the third triangle number is 6.
