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

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.

 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 NOW-NEXT 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 An = rAn - 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 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.