Topic Overview: Part 1: Factoring Quadratic Expressions Part 2: Understanding Basic Recursion

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 real-life events.

Explanation

A recursive function contains two important components:
1. A recursion formula that tells how any term of a sequence relates to the preceding terms (e.g., xn = xn - 1 + 2, or Next = Now + 2); and

2. An initial condition that gives the starting point
(e.g., x1 = 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 x1 = 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 = x2 can be used to determine the xth square number when you know the value of y. In contrast, the recursive formula for the square numbers is an = an - 1 + 2n - 1 where a1 = 1. To find the nth 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 y-intercept 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 an + 2 = an + 1 + an where a1 = 1 and a2 = 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 Now-Next 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 Now-Next 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, Now-Next 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 NOW-NEXT 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 Now-Next equation than writing an explicit formula. As an example, consider the table of values below. It may be easier for students to write a Now-Next equation than to write an explicit equation for the table below.

 x y 0 5 1 13 2 21 3 29 4 37

Now-Next Equation: Next = Now + 8, Start = 5
Linear Equation: y = 8x + 5

Writing a Now-Next 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 y-intercept 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 Now-Next 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 Now-Next 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 Now-Next equations such as
Now = Next + 8, Start = 5, with the formal notation an = an - 1 + 8, a0 = 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 y-intercept (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 E-Example at
http://standards.nctm.org/document/eexamples/chap7/7.2/index.htm,
and the entire collection of NCTM E-Examples is available at
http://standards.nctm.org/document/eexamples/.)

Sarah Wallick believes in teaching recursion because of its relevance to real life.

 Read transcript from Sarah Wallick It's a big topic in technology today ... Read More

 Next: Lesson Plans