☰ Contents Recursive Data

Building Up, with Code

Student: So I feel like I get the idea of recursion, but I don’t know how to turn your examples into code.
Prof: Let’s get back to your original idea – how would this look for Posts, in code?
Student: Do I have to write an interface first?
Prof: That’s how we’ve been doing it; at some point I’ll show you another way, but for this example that’s a good idea.
Student: OK so I need… an interface that represents posts? And then a recursive case and a base case.
Prof: Right – so the recursive case is the one you started with.
Student: A repost?
Prof: Right. And if you think about how posts work, what has to be at the end of a long chain of reposts?
Student: A… regular post?
Prof: Right! OK try turning that into code.
Student: Hmm so something like this?
Student: OHH so the base case just has the text. Like when you make one Tweet or whatever. I guess real posts have more stuff like images.
Prof: Absolutely, but you’ve captured the recursive structure now: try creating an instance now!
Student: OK…
Student: Wait, why didn’t that work?
Prof: This is an important detail: there are two uses of the Repost constructor in your program. One of them is taking a RegularPost, and the other is taking a Repost. But neither of those are Post values according to Java!
Student: Huh? I wrote the interface right there!
Prof: Do you remember anything from ImageQuery about something we need to add to record definitions?
Student: Oh! I need to say implements? Why?
Prof: Well, it’s how we tell Java “I want all Repost objects to count as Post objects; and I want all RegularPost objects to count as Post objects. It’s also one of the only ways to get this kind of sharing of classes with one type in Java.
Student: So without implements, there can never be a way to have Repost be a Post?
Prof: That’s right. Let’s fix it!
Prof: Nice! Let’s look at the memory diagram.
Names (the stack)
top level
r = @1003
Heap
@1001: RegularPost[message=I love to post]
@1002: Repost[message=what she said, original=@1001]
@1003: Repost[message=what he said, original=@1002]
Student: You know, this does just kind of look like nested data.
Prof: That’s a good observation. There’s a big difference between what you can create with something like your Post, Repost, and RegularPost, though. You can make a chain of Repost instances as long as you want. With types that describe just nested data, not recursive data, it always has to stop at some point. We’ll explore why that’s special by writing some recursive methods next.

Practice

Write an interface Ancestor, and two records that implement it: Known, with a String field name and two Ancestor fields parent1 and parent2, and Unknown, with no fields.



Ancestor me = new Known("Sam",
new Known("Pat", new Unknown(), new Unknown()),
new Unknown());

A Google Drive is made of docs and folders. Write an interface DriveItem, and two records that implement it: Doc, with a String field name and an int field sizeKb, and Folder, with a String field name and a field contents that is an array of DriveItems.



DriveItem drive = new Folder("My Drive", new DriveItem[] {
new Doc("resume", 40),
new Folder("photos", new DriveItem[] {
new Doc("cat", 300),
new Doc("dog", 280)
}),
new Doc("todo", 12)
});

Now the other way around. Here are records for math expressions. Write e, the expression (4 + 5) - x.

interface Expr {}
record Num(int value) implements Expr {}
record Var(String name) implements Expr {}
record Plus(Expr left, Expr right) implements Expr {}
record Minus(Expr left, Expr right) implements Expr {}

Expr e = ;

Course prerequisites can be written with just one record:

record Course(String name, Course[] prereqs) {}
Course cse11 = new Course("CSE 11", new Course[] {});
Course cse12 = new Course("CSE 12", new Course[] { cse11 });

There is no separate record for the base case. What plays the part of the base case here?

  1. A Course whose prereqs array is empty, like cse11
    cse11 doesn’t hold any other Course, because its array is empty. A chain of prerequisites stops at a course like that.
  2. A Course with something in its prereqs array, like cse12
    cse12 holds cse11 in its array, so it refers back to Course. That makes it a recursive case.
  3. The name field, because it is a String
    String doesn’t refer back to Course, but it isn’t a Course either. The base case has to be a value of the type itself.
  4. Nothing. Without a base record, no Course can ever be built
    We built cse11 without needing a Course first, so the data does have a place to stop.