Recursively Defined Sequences

We are already familiar with two methods of defining sequences. Write out the sequence listing the first few terms and allow the reader to guess the rest of the sequence, i.e. 3, 5, 7… Here a0 = 3, a1 = 5, a2 = 7, a3 =? Now, I intended to write the sequence of odd prime numbers, so a3 = 11. (To date, there is no explicit formula nor a recursive relation to describe the odd prime numbers.) A more formal way of defining a sequence is to give an explicit formula for its nth term: an = (-1)n / (n + 1), for all integers n ³ 0. Here a0 = 1, a1 = -1/2, a2 = 1/3, a3 = -1/4. A third way to define a sequence is to use recursion. Recursion requires a recurrence relation, which relates later terms in the sequence to earlier terms and a specification that provides values of the first few terms, called initial conditions. Consider a sequence, c0, c1, c2, c3… defined recursively as follows:

n! =

 1 if n = 0, initial conditions

=

 n(n –1)!
if n > 0. recurrence relation

What is 3! using our recurrence relation and initial conditions?
3! = 3(2!) = 3(2)(1!) = 3(2)(1)(0!) = 3(2)(1)(1) = 6.

Two advantages to this third way of defining a sequence are that:

  1. Recursion is a very succinct way of expressing certain mathematical functions.
  2. Corresponding programming implementation is also succinct.
The code for this recursive function in C++ is:
int Factorial (int n) {      
  if (n == 0)    // termination condition
    return 1;    
  else       
    return n * Factorial (n – 1); //recursive statement
}          

Notice that the function calls itself whenever the termination condition is not met. Each call to itself is with a smaller value. The function continues to "wind up" calling itself with successively smaller values until a call to itself is with a value meeting the termination condition. Then the function unwinds returning each value similar to our by hand calculation above
where 3! = 1(1)(2)(3) = 6.

As with mathematical induction, recursion can be used to solve complex larger problems using solutions to smaller subproblems. Note the analogy between the initial condition and basis step, and between the recurrence relation and inductive hypothesis.

One of the earliest examples of a recursively-defined sequence comes from the European mathematician Fibonacci, Leonardo of Pisa. In 1202 Fibonacci posed the following problem.

A single pair of rabbits is born at the beginning of a year. Assuming the following conditions:

  1. Rabbit pairs are not fertile during their first month of life but thereafter give birth to one new male/female pair at the end of every month (gestation is one month);
  2. No deaths occur during the year.

How many rabbits will there be at the end of the year?

The number of rabbit pairs alive at the end of month k

=

 The number of rabbit pairs alive at the end of month
k –1

+

 The number of rabbit pairs born at the end of month k

The key to solving this problem recursively is to recognize that the number of rabbit pairs born at the end of month k is equal to the number of rabbit pairs alive at the end of month k – 2. This is due to the rabbit pairs born at the end of month k – 1 not yet being fertile.

The number of rabbit pairs alive at the end of month k

=

 The number of rabbit pairs alive at the end of month
k –1

+

 The number of rabbit pairs alive at the end of month k – 2

The sequence generated is 1, 1, 2, 3, 5, 8, 13, 21, 34,…

The Fibonacci numbers are particularly interesting because they model many occurrences in nature. Some Fibonacci sequences/numbers found in nature: the number of branches in a tree, the number of petals on a flower (buttercups 5, asters 21, daises 34, 55, and 89), formula for making spirals. The ratio of Fn+1 to Fn as n becomes large is known as the golden ratio or golden mean. Consider F31/F30 = 1346269/832040 = 1.6180339887… The golden ratio is used as length versus width for windows, rooms, buildings, or even post cards.
The code for this recursive function in C++ is:
int Fibonacci (int n) {        
  if (n £ 2)    // termination condition
    return 1;      
  else        
    return Fibonacci (n – 1) + Fibonacci(n – 2); //recursive statement
}            

The function Fibonacci makes two recursive calls each time the termination condition is not met. The picture below shows the values returned by each of these function calls as the function unwinds. Recursive calls for computing F5:

Example Finding the square root of a positive real number.
Given the recurrence ak = (1/2)(ak - 1 + r / ak - 1), kÎ Z, k ³ 1, one can find the square root of any positive real number r by making an initial guess as to what ak - 1 might be.
Say we want to find the square root of 10 and we make an initial guess of ak - 1 = 3.

Write out the first four terms of this sequence to determine the square root of 10 (show all decimals).

a0 =

3

a1 = .5(3 + 10/3) =

3.16666666667

 

or carrying out fractions:.5(9/3 + 10/3) = .5(19/3) = 19/6 = 3 1/6

a2 = .5(19/6 + 10/(19/6)) =

3.16228070175

 

or carrying out fractions:.5(19/6 + 60/19) = .5(361/114 + 360/114) = .5(721/114) = 721/228

a3 =.5(721/228 +
10/(721/228)) =


3.16227766017



This method is known as the Newton-Raphson iterative method. The fourth term is accurate to all digits on my calculator when all digits are retained for each successive iteration. In a program one would terminate the iterations when the absolute value of the difference between successive terms was less than a predetermined tolerance.