Chapter ObjeCtives
After studying this chapter, you will be able to:
• Understand recursive definitions of sequences, collections of objects, and operations on objects.
• Write recursive definitions for certain sequences, collections of objects, and
operations on objects.
• Understand how recursive algorithms execute.
• Write recursive algorithms to generate sequences defined recursively.
• Find closed-form solutions for certain types of recurrence relations.
• Analyze algorithms by counting the number of executions of a basic unit of
work, either directly or by solving a recurrence relation.
You are serving on the city council’s Board of Land Management, which is considering a proposal by a private contractor to manage a chemical disposal site. The material to be stored at the site degrades to inert matter at the rate of 5% per year. The
contractor claims that, at this rate of stabilization, only about one-third of the original
active material will remain at the end of 20 years.
Question: Is the contractor’s estimate correct?
It is possible to check this estimate by doing some brute-force calculations: If
there is this much initially, then there will be that much next year, so much the following year, and so on through the 20 years. But a quick and elegant solution can
be obtained by solving a recurrence relation; recurrence relations are discussed in
Section 3.2.
Section 3.1 explores recursion, which is closely related to mathematical induction (discussed in the previous chapter) and is important in expressing many
definitions and even algorithms. Some sequences defined recursively can also
be defined by a formula. Finding such a formula involves solving a recurrence
relation; solution methods for several types of recurrence relations are developed in Section 3.2. Recurrence relations are an important tool in the analysis of
algorithms, which mathematically determines the amount of work a particular
algorithm must do. Analysis of algorithms is the topic of Section 3.3.
3
3
Recursion, Recurrence Relations,
and Analysis of Algorithms
C h a p t e r
157
After studying this chapter, you will be able to:
• Understand recursive definitions of sequences, collections of objects, and operations on objects.
• Write recursive definitions for certain sequences, collections of objects, and
operations on objects.
• Understand how recursive algorithms execute.
• Write recursive algorithms to generate sequences defined recursively.
• Find closed-form solutions for certain types of recurrence relations.
• Analyze algorithms by counting the number of executions of a basic unit of
work, either directly or by solving a recurrence relation.
You are serving on the city council’s Board of Land Management, which is considering a proposal by a private contractor to manage a chemical disposal site. The material to be stored at the site degrades to inert matter at the rate of 5% per year. The
contractor claims that, at this rate of stabilization, only about one-third of the original
active material will remain at the end of 20 years.
Question: Is the contractor’s estimate correct?
It is possible to check this estimate by doing some brute-force calculations: If
there is this much initially, then there will be that much next year, so much the following year, and so on through the 20 years. But a quick and elegant solution can
be obtained by solving a recurrence relation; recurrence relations are discussed in
Section 3.2.
Section 3.1 explores recursion, which is closely related to mathematical induction (discussed in the previous chapter) and is important in expressing many
definitions and even algorithms. Some sequences defined recursively can also
be defined by a formula. Finding such a formula involves solving a recurrence
relation; solution methods for several types of recurrence relations are developed in Section 3.2. Recurrence relations are an important tool in the analysis of
algorithms, which mathematically determines the amount of work a particular
algorithm must do. Analysis of algorithms is the topic of Section 3.3.
3
3
Recursion, Recurrence Relations,
and Analysis of Algorithms
C h a p t e r
157