☰ Contents Recursive Data

Building Up

Student: Professor, I was thinking about how social media posts work, and I think I have my own example of recursion! But it doesn’t work right.
Prof: Let’s have a look!
Student: So I was thinking about how you can repost someone’s post but add on your own text. But then someone else can repost your repost. And that seemed like recursive data. Here’s what I tried:
Prof: Oh super interesting. I totally agree that reposting is an example of recursive data, great observation!
Student: Here’s the issue: I can’t figure out how to create one. I wrote new
Post("check out this cool idea:", new Post(.... But then I didn’t know what to put in the parentheses. How do I make a Post without making a Post?

Prof: It’s frustrating right! There’s a good principle to learn here, though. All of the recursive data we’ve seen so far has a key feature: there are some records that have fields that refer back to the type, and some that don’t. For example in ImageQuery, the And and Or queries refer back to ImageQuery, but the ones that look directly at the image data like HasExtension or HasKeyword do not.

We call the ones with self-reference the recursive cases and the ones with no self-reference the base cases. What do you think some of the recursive and base cases of data are for Pict?

Student: Hmmm so I guess things like Beside are recursive cases, because they combine two Picts and Beside implements Pict.
Prof: Right, and the base cases?
Student: Those must be the simple shapes like Circle and Rect.
Prof: Right. We don’t need to construct a Pict to pass into a Circle, and a Circle doesn’t store another Pict. So this idea of base cases and recursive cases comes up over and over again in representing interesting data.
Student: Really?

Prof: Yeah, I’ll give a few more examples:

  • Math expressions like (4 + 5) - x → the base cases would be things like numbers and variable names. The recursive cases would be things like add and subtract expressions.
  • Files and folders in Google Drive → folders would be the recursive cases (because folders contain files and folders) and files would be base cases (files can’t contain folders).
  • Family trees of ancestors → people with known parents are the recursive cases (because they have parent fields that are also people), and the base cases are “unknown” places in the tree where there’s no information about an ancestor
Student: I’ll try one. In a course system, the courses are the recursive cases and the students in the course are the base cases.
Prof: Not quite! There’s no way for a course to contain a course, or a student to contain a student, so there’s no recursion in that example. It’s just nested data. That’s a really good example of the difference between data that is just nested, and data with a self-reference.
Student: Can I try another one?
Prof: Sure!
Student: OK so how about course prerequisites. An upper division course is a recursive case, because it has some prerequisites, like CSE12 requires CSE11, so CSE12 must have a field or something that stores CSE11. But CSE11 has no official prerequisites, so it is a base case?
Prof: Great example!

Practice

Which of these are recursive data? Select all that are.
  1. A repost on social media, with your own text added to someone else’s post
    A repost holds the post it reposts, and that post may be a repost too.
  2. A post on social media that mentions a user
    A post holds a user, but a user doesn’t hold a post, so nothing refers back to itself. This is nested data.
  3. An email forwarded with the original message inside it
    A forwarded email contains the original email, which may have been forwarded too.
  4. An email with some attachments
    An attachment is a file, and a file doesn’t hold an email. This is nested data.
  5. A folder of playlists, which can also hold other folders
    A folder holds playlists and other folders, and those folders hold more.
  6. A playlist of songs
    A playlist holds songs, and a song doesn’t hold a playlist. This is nested data.
  7. An org chart, where a manager has a list of the employees who report to them
    A manager’s reports are employees, and some of them are managers with reports of their own.
  8. An employee record that includes an office address
    An employee holds an address, and an address doesn’t hold an employee. This is nested data.

Here is a chain of reposts. Each post is either a regular post, or a repost that holds the post it reposts, shown inside it.

┌────────────────────────────────┐
│ @cy: "same, every week"        │
│ ┌────────────────────────────┐ │
│ │ @ben: "never"              │ │
│ │ ┌────────────────────────┐ │ │
│ │ │ @ana: "Does anyone's   │ │ │
│ │ │   code compile on the  │ │ │
│ │ │   first try?"          │ │ │
│ │ └────────────────────────┘ │ │
│ └────────────────────────────┘ │
└────────────────────────────────┘
Holding only the outer post, how far in do you have to look to answer each question?
Who wrote the outer post?
Is the outer post a repost?
Whose post did the outer post repost?
What did the regular post inside them all say?
How many posts are in the chain?