Lesson 1: Recursively defined structures

Overview

Summary: This lesson introduces a unifying theme in the course: the concept of recursion. Recursion refers to the process of computing something in terms of smaller or prior versions of itself. It is a computational technique, and a way of defining certain kinds of structures, that is common and powerful in computer science -- but also mysterious and not always well understood. In this lesson we will encounter recursion by looking at mathematical and computer science objects that are defined using recursive definitions.

This lesson addresses the following learning target(s):

• RI.1: I can construct several instances of a recursively defined structure, such as integer sequences, graphs, and trees.

Background

The factorial function is very commonly used in discrete mathematics. We can define the factorial function directly as follows:

Definition: Given a positive integer $n$, the factorial of $n$, denoted $n!$, is defined to be the number $n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1$. Additionally, we define $0!$ to be equal to $1$.

So for instance, $4!$ is $4 \times 3 \times 2 \times 1$, which equals $24$. We use the factorial a lot in counting arguments, because $n!$ counts the number of ways to take a collection of $n$ different objects and put them in order. For instance, look at the letters A, B, C, and D and try to arrange these in different order, like ABCD, ABDC, ACBD, and so on -- eventually you should come up with 24 different arrangements.

Did you notice that the factorial function has an interesting structure to it? In particular, the factorial function is computed in terms of smaller versions of itself. Here is an alternative definition of the factorial function that uses this structure:

Definition: Define $0!$ to be equal to $1$. Then, for any positive integer $n$, the factorial of $n$, denoted $n!$, is given by $n! = n \times (n-1)!$.

This seems strange -- it seems like there is really no definition happening here because we are defining $n!$ in terms of another factorial, namely $(n-1)!$. Does this definition really work? Let's try to compute $4!$ again using this new definition:

• Step 1: $4!$ is defined to be $4 \times 3!$. So... what is $3!$ equal to?

• Step 2: $3!$ is defined to be $3 \times 2!$. So... what is $2!$ equal to?

• Step 3: $2!$ is defined to be $2 \times 1!$. So... what is $1!$ equal to?

• Step 4: $1!$ is defined to be $1 \times 0!$. By definition, we know that $0! = 1$. Therefore $1! = 1 \times 0! = 1 \times 1 = 1$.

• Step 5: Now we have that $1! = 1$. Therefore $2! = 2 \times 1! = 2 \times 1$. Therefore $3! = 3 \times 2! = 3 \times (2 \times 1)$. Therefore $4! = 4 \times 3! = 4 \times (3 \times (2 \times 1))$ which equals $24$.

What just happened? We computed $4!$ by calling $3!$, that is by using a smaller, simpler factorial. Then we had to find $3!$ by calling $2!$, again a smaller and simpler factorial. Then we found $2!$ by calling $1!$ and $1!$ by calling $0!$. Then, finally, we have a definite numerical value for $0!$ -- namely, it's equal to $1$ -- and so we were able to back-substitute everything and eventually calculate all of the factorials we used.

This second definition of factorial that computes a factorial in terms of smaller factorials is called a recursive definition, and the computation that we did uses recursion.

A recursively defined structure -- like the factorial of an integer -- is a lot like a set of Russian dolls, like the ones shown in the video:

(Direct link: https://www.youtube.com/watch?v=aNQV45Wichw)

It looks like one doll at first, but then you open it up to find a smaller doll inside, which has another smaller doll inside, which has another smaller doll inside, and so on -- until you end up with one, tiny doll that cannot be reduced down any further. Then, at that point you have the whole family of dolls.

Can we compute the factorial of a negative integer, like $(-3)!$? Let's try using the recursive definition and see what happens:

• The definition would say that $(-3)!$ is equal to $(-3) \times (-4)!$ because the new factorial is one less than the previous one.

• Then we would recursively call the definition on $(-4)!$, which would give us $(-3)! = (-3) \times ((-4) \times (-5)!$.

• Then we would recursively call the definition on $(-5)!$, which would give us $(-3)! = (-3) \times \left((-4) \times ((-5) \times (-6)!)\right)$.

We'll stop at this point, because do you see what's happening? We're stuck in an infinite process. When we were computing $4!$, the process ended because we subtracted 1 repeatedly and eventually hit 0, whose factorial value we had defined to equal $1$. But here, we can keep on subtracting 1 but we will never "hit bottom". The process just continues forever.

This means that there are two essential ingredients to a correctly-formed recursive definition of a structure:

1. There must be a rule for how to construct the structure from previous, simpler versions of the structure. And,

2. There must be a base case that allows us to make a computation without recursion.

In our definition of the factorial, the rule was that $n! = n \times (n-1)!$ when $n$ is a positive integer; and the base case is the declaration that $0! = 1$.

Another kind of structure that can be recursively defined are integer sequences. Here is a famous example:

Definition: The Fibonacci sequence is the sequence of integers given by $$1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \dots$$ The first number in the sequence is denoted $F_1$, the second $F_2$, and so on. The Fibonacci sequence is defined recursively as follows:

• (Base case) We define $F_1 = 1$ and $F_2 = 1$.

• (Recursive rule) For all $n > 2$, define $F_n = F_{n-1} + F_{n-2}$. (That is, each Fibonacci number starting with the third one is the sum of the previous two Fibonacci numbers.)

So for example, what is $F_6$? We can see from the sequence that it should be $8$, but if that list of integers weren't there and all we had was the definition, how would we know? According to the definition, $F_6$ equals $F_5 + F_4$. Now we'll "unpack" each of $F_5$ and $F_4$ using the definition. Every set of nested parentheses below is an instance of this "unpacking". Remember we don't have to "unpack" $F_2$ or $F_1$ because those are defined to be equal to $1$.

Since each of these numbers on the right now equals 1 by definition, we can plug in $1$ for each of them and see that $F_6 = 8$.

Here's one more example to illustrate the idea that recursively defined structures are not always numbers or sequences of numbers. This has to do with strings. A palindrome is a word that is spelled the same forwards as it is backwards, like RACECAR or NOON or KAYAK. We can extend this idea to say that any string of characters, so for example the string XYQQZQQYX is a palindrome. What's a way to formally define a palindrome? Here is a recursive definition:

Definition: Let $\lambda$ be a string of characters from the English alphabet. The empty string is defined to be a palindrome. A single character is also defined to be a palindrome, and a two-letter string formed from the same letter (for example RR) is a palindrome. Finally, if $\alpha$ is any single character and $\lambda$ is a palindrome, then the string $\alpha + \lambda + \alpha$ is also a palindrome where + stands for concatenation of strings (as in Python).

This is a recursive definition because it gives appropriate base cases (the empty strings and single letters are defined to be palindromes, which makes sense) and then a way of generating a new palindrome out of smaller ones.

Let's play with that definition to get a few examples.

• According to the base case, we can pick any letter we want and it's a palindrome, so K is a palindrome.

• Since K is a palindrome, according to the recursive rule I can choose any other character I wish and sandwich K in between them, and I will have another palindrome, so for example EKE is a palindrome.

• Since EKE is a palindrome, so is REKER for example. And so would be PREKER, ZPREKERZ, and so on.

• Another basic example would be NN. So another palindrome could be ANNA, and therefore BANNAB, and so on.

This recursive definition allows you to construct something, namely a palindromic string. This might be useful if, for example, we wanted to write a computer program that accepts a string as input and determines whether it is a palindrome.

Other resources for learning

NOTE: The resources below are supplemental, not required. They are here for you to get alternate presentations of concepts and additional examples. Use as many or as few of these as you wish.

• This tutorial from Khan Academy is a nice short introduction to recursion and contains some of the ideas developed here: https://www.khanacademy.org/computing/computer-science/algorithms/recursive-algorithms/a/recursion

• Below is a video made for MTH 210 (Communicating in Mathematics) at GVSU on recursively defined sequences:

(Direct link: https://www.youtube.com/watch?v=txdmCgThR6o)

Preview Activities

NOTE: Preview Activities are to be done in your own notes, for your reference later. However you will be asked to submit your work using a Google Form using the link given below in the "Submission Instructions" area. It is highly recommended that you do your work on paper, then type out your answers into a text editor or note-keeping software (like Evernote, OneNote, etc.), then copy/paste the answers into the Google Form. You will not have access to your answers once you submit them (hence the idea of keeping them in a text editor or note-keeping tool). We will discuss the answers briefly in class (see dates below).

Also, recall that Preview Activities are graded either Pass or No Pass. The criteria for earning a Pass grade are:

• All questions must have a complete answer. Submissions in which parts of questions are unaddressed or left blank will receive No Pass.

• All answers must represent a good faith effort to be right. This means that you have done your best to give a correct response. Responses that consist of questions or expressions of confusion (such as "I didn't understand what the question was asking") will receive No Pass. If you have a question, go to the discussion board and ask your question or come to office hours.

• Answers must be submitted prior to one hour before class time (see below); late submissions will receive No Pass.

• Please note that mathematical correctness is not a grading criterion on Preview Activities.

Activities

1. The Gibonacci sequence is an integer sequence defined recursively by: $G(0) = 5$, $G(1) = 6$, $G(2) = 7$, and $G(k) = G(k-1) - G(k-2) + G(k-3)$ for $k \geq 3$. Write out the first 15 members of the Gibonacci sequence. (You are already given the first three.)

2. Here is a set that is recursively defined. Call the set $S$. The set $S$ consists of strings, as follows: We will define the letter a to belong to the set $S$ and the letter b to belong to $S$. Additionally, for any element $x$ of $S$, the string $ax$ and the string $bx$ also belong to $S$. At the response form, there is a multiple-selection question that lists several strings; check all the strings that belong to $S$. (Note that $x$ is a string that is an element of $S$; it does not mean literally the letter x.)

3. The final "activity" for you to do is to write out any specific mathematical questions you have about the material in this lesson. There's a large text box for you to do so.

Submission instructions

Please submit your work using the Google Form located here: http://bit.ly/1MJqPNB

Again, you are strongly encouraged to do your work on paper, type up your answers and save them in a text editor or note-keeping tool, and then copy/paste the answers into the Google Form because you will not be able to access the answers once they are submitted.

You are to submit your answers no later than one hour before your section's class meeting on Friday, January 15. Late submissions are automatically marked No Pass. We will take the first few minutes of class on that date to debrief the answers and address any major, widespread misconceptions.

Daily Homework

About Daily Homework: Daily Homework consists of problems to work that will have you dig deeper into the concepts of this lesson and serve as raw material for class discussion. You are expected to write out complete solutions on paper (electronic notes are OK too) and have these ready to be checked during class. During class, you will work with other students to work through and correct your solutions and also to present your work at the board. We will also use class time to build on your Daily Homework to explore more advanced topics, so giving a good-faith effort to complete all your Daily Homework is essential to understand the rest of the class meeting.

Daily Homework is graded Pass or No Pass on the basis of whether the solution that you bring to class is complete and shows a good-faith effort to be right on each problem. Correctness is not a criterion; you'll work to correct your solutions in small groups.

Here are the problems for Daily Homework for Lesson 1, which will be discussed in class on Wednesday January 20:

1. Generate the first 10 terms of each of the following sequences.

   • $a_n = a^2_{n-1}$, where $a_1 = 2$

   • $a_n = n a_{n-1} + n^2 a_{n-2}$, where $a_0 = 1$ and $a_1 = 1$

2. The binomial coefficient $C(n,k)$ (where $n,k \in \mathbb{N}$) is an expression that counts the number of ways to select $k$ objects from a group of $n$ objects without considering the order in which they are chosen. It can be defined in two ways. A direct formula for the binomial coefficient is $$C(n,k) = \frac{n!}{k! (n-k)!}$$ For example, $C(5,3) = \frac{5!}{3! (5-3)!} = \frac{5!}{3! 2!}= 10$ and counts the number of ways to select a group of three people out of a group of five without considering order. However, we can also define the binomal coefficient recursively as follows. First of all, for all define for all $n \in \mathbb{N}$: $$C(n,0) = 1 \qquad \text{and} \qquad C(n,n) = 1$$ And for any $k \in \mathbb{N}$, define: $$C(n,k) = C(n-1, k-1) + C(n-1,k)$$ Trace through the steps of this recursive algorithm to show that $C(5,3) = 10$ as explained above. In the class meeting, your group may be called upon to apply this recursive definition to a different pair of numbers so we can have two examples on the board.

3. Define the function maxList to accept a nonempty list of integers as its input, and the output is the largest element in the list. For example, maxList([-3,2,0,5]) = 5. Below is a possible recursive definition for this function. Before we give that definition, there are three helper functions we will define:

   • max accepts two integers (not in a list) and returns the larger of the two. For example, max(-5, 2) = 2.

   • first accepts a list and returns the first item in the list. For example, first([a,b,c,d]) = a.

   • tail accepts a list and returns the list without its first element. For example, tail([a,b,c,d]) = [b,c,d].

   Now here is the recursive definition:

   • Define maxList([x]) = x whenever the input is a single-element list.

   • Otherwise define maxList(L) = max(first(L), maxList(tail(L))).

   Walk through the steps of the recursive definition to compute maxList([-4,5,7,1,-9,2, 3, 0]). (The answer is obviously 7, so the steps are what matter.) In the class meeting, your group may be called upon to apply this recursive definition to a different list so we can have two examples on the board.