
Course 3 Unit 7  Recursion and Iteration
©2009
Although the words "recursion" and "iteration" have
not, up to this point, been explicitly used in CorePlus Mathematics,
they represent a key theme in the curriculum, primarily as seen so
far in terms of work with NOWNEXT rules. Recursion and iteration
are powerful tools for representing and solving problems related to
sequential change. Sequential change is stepbystep change,
such as population change yearbyyear. 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
over again.
Unit Overview 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 A_{n} = rA_{n  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 firstorder linear
difference equations with constant coefficients. In Lesson 1,
realworld 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.
CPMPTools The
spreadsheet software in CPMPTools 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
tool.
Objectives
of the Unit
 Use iteration
and recursion as tools to represent, analyze, and solve problems
involving sequential change
 Formalize
and consolidate previous study of NOWNEXT rules,
particularly through the use of subscript notation and the
introduction of recursive formulas
 Understand
and apply arithmetic and geometric sequences and series
 Understand
and apply finite differences tables
 Explore
function iteration and, in the process, informally introduce
function composition
 Understand
and apply recursive formulas, particularly combined recursive
formulas of the form A_{n} = rA_{n  1} + b
 Review
linear, exponential, and polynomial models from a recursive
perspective

Sample Overview 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 NOWNEXT 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 longterm population of the fish
pond is not dependent on the starting population but only on the dieoff
rate and the restocking amount.
Instructional
Design 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 fourphase cycle of classroom activities—Launch,
Explore, Share and Summarize, and Apply.
This instructional model is elaborated under Instructional
Design.
View the
Unit Table of Contents and Sample Lesson Material You will need the
free Adobe
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 14
descriptions.)
