Recursive Sequences

by Justin Skycak (@justinskycak) on January 03, 2021

Sequences where each term is a function of the previous terms.

This post is part of the book Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents. Suggested citation: Skycak, J. (2021). Recursive Sequences. In Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents. https://justinmath.com/recursive-sequences/

Want to get notified about new posts? Join the mailing list and follow on X/Twitter.

A recursive sequence is a sequence where each term is 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:

$\begin{align*} 3, 7, 15, 31, 63, 127, 255, 511, \ldots \end{align*}$

Implementing Recursive Sequences

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. This way, we don’t have to bother storing any intermediate values.


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

Exercises

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 $2,-3,$ generate each term by adding the product of the previous two terms.

Want to get notified about new posts? Join the mailing list and follow on X/Twitter.