Course 3 Unit 7 - Recursion and Iteration
©2009

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 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 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.

CPMP-Tools The 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 tool.

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 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.

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 four-phase 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.

• Unit Table of Contents and Lesson 1 SE Sample (2.01 MB)
  

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 descriptions.)