


Part 2: Understanding Basic Recursion
Recursion is the process of describing the next term in a sequence in relation to preceding terms. Recursive formulas can model population growth patterns, the distance traveled on a trip, the interest earned on a bank account, and other reallife events.
Explanation
A recursive function contains two important components:
 A recursion formula that tells how any term of a sequence relates to the preceding terms
(e.g., x_{n} = x_{n  1} + 2, or Next = Now + 2); and
 An initial condition that gives the starting point
(e.g., x_{1} = 1 or Start = 1).
The initial condition is necessary to ensure a uniquely defined sequence. The example above gives the sequence of odd numbers 1, 3, 5, 7, ... . However, if the initial condition was modified to
x_{1} = 2 or Start = 2, the recursive function would give the sequence of even numbers 2, 4, 6, 8, ... .
Unlike a recursive formula, an explicit formula stands alone; that is, it has no additional qualifiers. The explicit formula y = x^{2} can be used to determine the
x^{th} square number when you know the value of y. In contrast,
the recursive formula for the square numbers is
a_{n} = a_{n  1} + 2n  1 where a_{1} = 1. To find the n^{th} square number, you first need to find the previous n  1 square numbers.
Other examples:
 The linear function y = 60x + 230, which describes the line with yintercept 230 and slope 60, can be used to represent the distance from home (y) of a traveler who began the day 230 miles from home and drives at 60 miles per hour for x hours. Defined recursively, this relationship would be Next = Now + 60 where Start = 230.
 The balance of a bank account that earns 3% a year can be defined recursively as Next = Now + 0.03 * Now or as Next = 1.03 * Now. If the beginning balance in the account was $248, then Start= 248.
 In the game of Monopoly®, players may need to roll doubles to get out of jail. When rolling two dice, the probability of getting doubles is 1/6. The recursive formula Next = Now * 5/6, Start = 1/6 describes the probability of getting doubles for the first time on exactly the nth roll (meaning that doubles were not obtained on any previous roll.)
 The Fibonacci sequence is most often defined by the recursive formula
a_{n + 2} = a_{n + 1} + a_{n} where a_{1} = 1 and a_{2} = 1; that is, each term is equal to the sum of the previous two terms, and the sequence begins
1, 1, 2, 3, 5, 8, 13, 21, ... However, it would not be possible to write this equation using the NowNext form because you have to reference the previous two terms instead of only the previous term.
Mathematical Definition
A recursion (or a recursive function) is an expression, such as a polynomial, each term of which is determined by application of a formula to preceding terms. The formula must include a start or seed value.
Role in the Curriculum
Informally, recursive functions are sometimes called NowNext equations because they describe the next term in relation to the current, or now, term. In addition to laying the foundation for a more formal study of recursion, NowNext equations provide an alternate form of representation and help students learn to develop an explicit equation.
Read what teacher educator Carol Malloy has to say about the role of recursion in developing mathematical understanding:




Read transcript from teacher educator Carol Malloy 






This lesson is a precursor to students working with sequences and series...
Read More

The National Council of Teachers of Mathematics (NCTM) suggests in Principles and Standards of School Mathematics (PSSM) , "Another type of representation that teachers might wish to introduce their students to is a NOWNEXT equation, which can be used to define relationships among variables iteratively. The equation NEXT=NOW+10 would mean that each term in a pattern is found by adding 10 to the
previous term." (NCTM, PSSM, p. 284).
With many sequences, it may be easy to identify how terms change from one to the next. Consequently, students will sometimes have less difficulty writing a NowNext equation than writing an explicit formula. As an example, consider the table of values below. It may be easier for students to write a NowNext equation than to write an explicit equation for the table below.
x 
y 
0 
5 
1 
13 
2 
21 
3 
29 
4 
37 

NowNext Equation: Next = Now + 8, Start = 5
Linear Equation: y = 8x + 5
Writing a NowNext equation may also help students to develop explicit formulas. Both equations contain an 8, and students should see in both cases that 8 represents the amount of change between terms. Both equations also contain a 5, which is the yintercept and the initial condition of the recursive equation.
Educator Sarah Wallick realizes that students may have a preference for either recursive or explicit equations, which is why she believes in teaching both. Sarah explains, "When kids are just getting started, they are coming at it from lots of different places. Some kids, when they look at a table of values, immediately go into a recursive mode. They will look at the relationship from one y value to the next y value in the table."
For these kids, learning about recursive formulas and NowNext equations is not only necessary to ensure they understand various representations, it may be the only way they can understand and interpret the mathematics of the situation.
Sarah continues, "Other kids look at the relationship and immediately connect whatever the x is to the y. They are working in the explicit mode."
For these students, seeing NowNext equations introduces them to an alternate representation, and it pushes them to think about the relationship in a slightly different way.
NCTM advocates that students understand the relationship between recursive and explicit formulas. In discussing a population growth problem, PSSM states, "Some students might generate an iterative or recursive definition for the function, using the population of a given year (NOW) to determine the population of the next year (NEXT):
NEXT=(1.02)*NOW, start at 6 billion
Moreover, students should be able to recognize that this situation can be represented explicitly by the exponential function f(n)=6(1.02)^{n}, where f(n) is the population in billions and n is the number of years since 1999." (NCTM, PSSM, 2000, p. 298).
Working with recursion formulas in algebra lays the foundation for the later study of sequences and series. Conceptually, understanding sequences and sequence notation is sometimes difficult for students. An adequate introduction to recursive formulas will help students make the transition seamlessly. The study of sequences and series in later math courses involves determining the initial condition and transitioning from recursive to explicit formulas and vice versa. It also involves replacing NowNext equations such as
Now = Next + 8, Start = 5, with the formal notation a_{n} = a_{n  1} + 8, a_{0} = 5.
Students may have difficulty identifying the start value. In the Workshop 5 video, some students chose the first term as the start value; others chose the yintercept (or zero term). As Carol Malloy says, either is acceptable at the Algebra 1 level as long as the students can justify their choice.
When selecting situations for students to model, NCTM suggests that teachers "include examples in which models can be expressed in iterative, or recursive, form." (NCTM, PSSM, p. 302). One of the examples that NCTM recommends involves the elimination of medicine from the body, based on a problem originally developed by the National Research Council. (For a discussion of this problem, see page 302 of PSSM, available online at
http://standards.nctm.org/document/chapter7/alg.htm.
This problem is available as an EExample at
http://standards.nctm.org/document/eexamples/chap7/7.2/index.htm,
and the entire collection of NCTM EExamples is available at
http://standards.nctm.org/document/eexamples/.)
Sarah Wallick believes in teaching recursion because of its relevance to real life.






