Section 3.1 Recursive Definitions
171
S e c t I o n 3 . 1 Review
technIQueS
• Generate values in a sequence defined recursively.
• Prove properties of the Fibonacci sequence.
• Recognize objects in a recursively defined collection of objects.
• Give recursive definitions for particular sets of
objects.
• Give recursive definitions for certain operations on
objects.
• Write recursive algorithms to generate sequences
defined recursively.
maIn IDeaS
• Recursive definitions can be given for sequences of
objects, sets of objects, and operations on objects
where basis information is known and new information depends on already known information.
• Recursive algorithms provide a natural way to
solve certain problems by invoking the same task
on a smaller version of the problem.
table 3.1
recursive Definitions
What Is being Defined
characteristics
Recursive sequence
The first one or two values in the sequence are known; later items in the sequence are
defined in terms of earlier items.
Recursive set
A few specific items are known to be in the set; other items in the set are built from
combinations of items already in the set.
Recursive operation
A “small” case of the operation gives a specific value; other cases of the operation are
defined in terms of smaller cases.
Recursive algorithm
For the smallest values of the arguments, the algorithm behavior is known; for larger
values of the arguments, the algorithm invokes itself with smaller argument values.
W
exercISeS 3.1
For Exercises 1–12, write the first five values in the sequence.
1. S(1) = 10
S(n) = S(n − 1) + 10 for n ≥ 2
2. C(1) = 5
C(n) = 2C(n − 1) + 5 for n ≥ 2
3. A(1) = 2
A(n) =
1
A(n − 1)
for n ≥ 2
4. B(1) = 1
B(n) = B(n − 1) + n
2
for n ≥ 2
5. S(1) = 1
S(n) = S(n − 1) +
1
n
for n ≥ 2
6. T(1) = 1
T(n) = nT(n − 1) for n ≥ 2