Course 3 Unit 7 - Recursion and Iteration
Although the words "recursion" and "iteration" have
not, up to this point, been explicitly used in Core-Plus Mathematics,
they represent a key theme in the curriculum, primarily as seen so
far in terms of work with NOW-NEXT rules. Recursion and iteration
are powerful tools for representing and solving problems related to
sequential change. Sequential change is step-by-step change,
such as population change year-by-year. Recursion is the method
of describing a given step in a sequential process in terms of previous
steps. Iteration is
the process of repeating the same procedure or computation over and
This unit formalizes
the development of recursion and iteration while exploring some common
applications, like compound interest, and related topics, such as arithmetic
and geometric sequences. The major topics in this unit are recursive
formulas (also called recurrence relations, recurrences, or difference
equations), arithmetic and geometric sequences, arithmetic and geometric
sums, finite differences, and function iteration (which implicitly
includes function composition). The unit also provides a review of
linear, exponential, and polynomial functions.
In a sense, this
unit is mainly about recursive formulas of the form An = rAn - 1 + b.
Such recursive formulas can be called combined recursive formulas because
they are a combination of the basic recursive formulas that give rise
to arithmetic and geometric sequences. Recursive formulas of this form
have several different names in discrete mathematics texts. For example,
they are also called affine recurrence relations or first-order linear
difference equations with constant coefficients. In Lesson 1,
real-world situations are modeled with combined recursive formulas.
In Lesson 2, students investigate combined recursive formulas
with r = 1, producing arithmetic sequences, and combined
recursive formulas with b = 0, producing geometric
sequences. In Lesson 3, the emphasis is on iterating linear functions,
which corresponds to sequentially evaluating combined recursive formulas.
spreadsheet software in CPMP-Tools can be used to examine sequences
and (term number, sequence value) scatterplots. The "Function Iteration" custom
tool has been developed for Lesson 3. Select "Course 3" from the Course menu.
Under the Algebra menu, you will find the Spreadsheet software and
the "Function Iteration" custom
of the Unit
- Use iteration
and recursion as tools to represent, analyze, and solve problems
involving sequential change
and consolidate previous study of NOW-NEXT rules,
particularly through the use of subscript notation and the
introduction of recursive formulas
and apply arithmetic and geometric sequences and series
and apply finite differences tables
function iteration and, in the process, informally introduce
and apply recursive formulas, particularly combined recursive
formulas of the form An = rAn - 1 + b
linear, exponential, and polynomial models from a recursive
The main focus of
the unit in general and this investigation in particular is to examine
the behavior of recursive formulas, starting with the familiar NOW-NEXT rules.
Investigation 1 of Lesson 1 is frequently a delight for students
and teacher alike, as it is both practical and puzzling. Your students
may be surprised to discover that the long-term population of the fish
pond is not dependent on the starting population but only on the die-off
rate and the restocking amount.
Throughout the curriculum,
interesting problem contexts serve as the foundation for instruction.
As lessons unfold around these problem situations, classroom instruction
tends to follow a four-phase cycle of classroom activities—Launch,
Explore, Share and Summarize, and Apply.
This instructional model is elaborated under Instructional
Unit Table of Contents and Sample Lesson Material
You will need the
Acrobat Reader software to view and print the sample material.
How the Discrete
Mathematics Strand Continues
In Course 4:
Preparation for Calculus Unit 8, Counting Methods and Induction,
students study the following topics: systematic listing and counting,
counting trees, the Multiplication Principle of Counting, Addition
Principle of Counting, combinations, permutations, selections with
repetition, the binomial theorem, Pascal's triangle, combinatorial
reasoning, the general multiplication rule for probability, the Principle
of Mathematical Induction, and proof using the Least Number Principle. (See
the CPMP Courses 1-4