# Recursive Sequences

A **recursive sequence** is a sequence where one or more terms are given and each following term is defined as a function of the previous terms. For example, consider the following rule for generating a recursive sequence: starting with $3,$ generate each term by doubling the previous term and adding $1.$ The terms of this sequence are as follows:

One way to implement recursive sequences in code is to store all terms in an array. For example, a function that returns the first $n$ terms of the recursive sequence “starting with $3,$ generate each term by doubling the previous term and adding $1$” could be implemented as follows:

```
def calc_first_n_terms(n):
terms = [3]
while len(terms) < n:
prev_term = terms[-1]
next_term = 2 * prev_term + 1
terms.append(next_term)
return terms
```

If all we want is the $n$th term, then it can sometimes be more convenient to make the implementation itself recursive:

```
def calc_nth_term(n):
if n == 1:
return 3
else:
prev_term = calc_nth_term(n-1)
return 2 * prev_term + 1
```

To understand how the function above works, first notice that `calc_nth_term(1)`

will return $3.$ This is called the **base case**. If a different input is passed, then the function will keep calling itself in a lower input until it reaches the base case.

```
calc_nth_term(4)
|--> prev_term = calc_nth_term(3)
|--> prev_term = calc_nth_term(2)
|--> prev_term = calc_nth_term(1)
|--> return 3
|<--
|<-- return 2 * 3 + 1 = 7
|<-- return 2 * 7 + 1 = 15
|<-- return 2 * 15 + 1 = 31
Output: 31
```

*Practice Problems*

Several different recursive sequences are described below. For each sequence, write a function to generate an array containing first $n$ terms, and then write a separate *recursive* function to generate the $n$th term. Be sure to work these sequences out by hand and write tests.

- Starting with $5,$ generate each term by multiplying the previous term by $3$ and subtracting $4.$
- Starting with $25,$ generate each term by taking half of the previous term if it's even, or multiplying by $3$ and adding $1$ if it's odd. (This is an instance of a
*Collatz sequence*.) - Starting with $0,1,$ generate each term by adding the previous two terms. (This is the famous
*Fibonacci sequence*.) - Starting with terms $2,-3,$ generate each term by adding the product of the previous two terms.

## Leave a Comment