### Unit 7: Recursion

In previous sections, we learned about sequences in a general sense. In this unit, we will take a look at a specific type known as a recursive sequence. The unit will first present a number of examples that demonstrate how one computes the terms of a recursive sequence and analyzes certain kinds of problems recursively in order to generate a general recursive sequence. We will then learn to use the proof method of induction to prove the validity or falsity of a recursive sequence.

In this unit, we are going to rely on the Bender and Williamson reference as primary. Use the Devadas and Lehman reference as supplementary. Switching primary references exposes us to some differences in notation and perspective.

**Completing this unit should take you approximately 9 hours.**

Upon successful completion of this unit, you will be able to:

- compute recursively defined sequences;
- solve recursive relations; and
- explain important recursive functions, including McCarthy's 91 and Ackermann.

### 7.1: Recursively Defined Sequences

Read Section 4, "Recursion Equations," up to example 27 on pages DT-42 - DT-46.

Notice that the definition of induction, in "Unit IS: Induction, Sequences and Series," is in terms of A(n), an assertion dependent on n. The A(n), n = 1, ..., n, ... is a sequence. In induction, A(n-1) is used to prove A(n). If A(n) is defined using A(n - 1), the sequence is recursively defined. Thus, induction and recursion both exploit a relationship between A(n) and A(n-1).

Given a recursive relation, the terms of its recursively defined sequence are computed by evaluating the relation for the base value, say n = 1, then evaluating it for successive values of n.

Given a recursive equation, also called a recursive relation, Theorem 7 on page DT-43 of the reading in Subunit 7.1 tells us how to verify a solution for it.

Let f(n) be an explicit formula for the nth term, A

_{n}, of a sequence and assume that f(n) = A b_{n}+ K = A b_{n}+ K + Kb - Kb = A b_{n}+ Kb + K - Kb = b (A b_{n}-1 + K) + K ( 1 - b) = b f(n - 1) + K(1 - b). Thus, f(n) = b f(n - 1) + C, a recursive equation, i.e. relation.For the Fibonacci numbers, see theorem 9 and example 29 on pages DT-48 - DT-49. Example 29 starts with the sequence, F0 = F1 = 1, Fk = Fk -1 + Fk -2, and develops a formula for Fn which does not utilize an earlier F in the sequence.

For the Towers of Hanoi problem, see example 11 on pages DT-18 - DT-19.

This example solves a famous puzzle with a recursive solution, namely a solution for n discs in terms of a solution for n-1 and 1 discs.

This reading presents an alternative illustration of the use of a recursive equation to solve the Tower of Hanoi problem. Read Section 1 on pages 1 - 5.

### 7.2: Solving Recurrence Relations

Read from example 27 to the end of the chapter on pages DT-46 - DT-50

A solution to a recursive equation is a formula that computes A(n) without having to compute A(k), for k < n. Review the section on "Recursive Equations," on page DT-44 up to example 26 on page DT-46.

1. A solution to a recursive equation can be found by inspection of the terms of a given sequence (example 27); OR 2. Apply theorem 8 if A(n) depends on A(n - 1) and theorem 9, if A(n) depends on A(n - 1) and A(n - 2).

Regarding Theorem 8 on page DT-48, if a

_{n}= ba_{n}- 1 +c , then iterating, a_{n}= b( ba_{n - 2}+c) + c = b(b (b a_{n - 3}+ c ) + c ) + c= ....= a_{0}b_{n}+ c b_{n-1}+ c b_{n-2}+ .... + c. This is an example of using the method of iteration for finding a formula for a recurrence relation for an arithmetic sequence.

### 7.2.1: Finding a Formula for an Iterative Relation for a Geometric Sequence

A simple example of going from an iterative relation to a formula is as follows: given the iterative relation, a

_{n}= ar_{n}, ar_{n}, = r a r_{n-1}= r a_{n - 1}, . Continuing in this manner, we get the formula, an = r_{n}a_{0}.For another example, read over Exercise 4.7 on page DT-51. It discusses going from an iterative sequence to a recursive solution/equation, and vice versa, from the recursive equation to an iterative sequence.

Note that you have already read this lecture in Subunit 4.2. Focus on re-reading Section 1.2 on page 3, which finds a formula not for the terms of the sequence, but for the sum of the terms of the sequence.

### 7.2.2: Using Mathematical Induction

Read Section 4 on pages DT-42 to DT-44 up to "Recursion Equations." Note that mathematical induction and recursion are closely related concepts.

### 7.3: Recursive Functions

### 7.3.1: McCarthy's 91 Function

Read the Wikipedia article for a description of the McCarthy 91 function, an example of a recursive function used in computer science as a test case for the performance of formal verification techniques and methods.

### 7.3.2: The Ackermann Function

Read the Wikipedia article for a description of the Ackermann function, an example of a recursive function that grows very rapidly.

### Unit 7 Assessment

Take this assessment to see how well you understood this unit.

- This assessment
**does not count towards your grade**. It is just for practice! - You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
- You can take this assessment as many times as you want, whenever you want.

- This assessment