☰ Contents Recursive Data

Recursive Methods

Student: How do I know how to make methods for recursive data?
Prof: It can take a little practice! But the split of base case and recursive case helps a lot. The idea is that we implement the method in each class that is part of our recursive data definition – this is called structural recursion specifically, and it matches the examples we’ve seen so far.
Student: So to implement a method I have to implement the same method over and over?
Prof: Kind of! And we’ve seen this a few times. Like for the matches method, we had a method body for HasExtension, and a method body for HasKeyword, and a method body for Or, and so on. Each one handled just the behavior specific to its class. In the case of recursive cases like Or, it called the same method on its pieces to get its result.
interface ImageQuery { boolean matches(ImageData im); }
record HasExtension(String ext) implements ImageQuery {
  public boolean matches(ImageData im) { ... ext ... }
}
record HasKeyword(String keyword) implements ImageQuery {
  public boolean matches(ImageData im) { ... keyword ... }
}
record Or(ImageQuery q1, ImageQuery q2) implements ImageQuery {
  public boolean matches(ImageData im) { ... q1.matches(im) ... q2.matches(im) ... }
}
record And(ImageQuery q1, ImageQuery q2) implements ImageQuery {
  public boolean matches(ImageData im) { ... q1.matches(im) ... q2.matches(im) ... }
}
Prof: The same kind of shape is true of Pict
interface Pict { int width(); /* plus many more methods */ }
record Circle(int radius, String color) implements Pict {
  public int width() { ... radius ... }
}
record Rect(int width, int height, String color) implements Pict {
  public int width() { ... width ... }
}
record Beside(Pict left, Pict right) implements Pict {
  public int width() { ... left.width() ... right.width() ... }
}
record Above(Pict top, Pict bottom) implements Pict {
  public int width() { ... top.width() ... bottom.width() ... }
}
Student: Hey, you left out a lot of detail in these!
Prof: That’s on purpose – I want to illustrate a common shape between these. In all the base cases, the methods worked with just the parameters of the method, and the fields of the class. So width for a Circle uses the radius, matches for HasKeyword uses the keyword, and so on. In contrast the recursive cases make recursive calls using the same-named method on their pieces. It’s a general pattern!
interface RecursiveData { Type recMethod(Param p, ...); }
record BaseCase(Field field, ...) implements RecursiveData {
  public Type recMethod(Param p, ...) { ... field ... }
}
record RecCase(Field field, ... RecursiveData d, ...) implements RecursiveData {
  public Type recMethod(Param p, ...) { ... field ... d.recMethod(p, ...) ... }
}
// Could be several different BaseCase and RecCase classes for a recursive data
// definition, not just base and rec
Student: Hmmm I think I’m starting to see. So the recursive case will always have a field that refers back to the interface?
Prof: That’s right. Think you can apply it to your Post now?
Student: So I already have the outline of my base case and my recursive case. I need to pick a method to try. Maybe like… if a word shows up anywhere in the chain of reposts? Like a search?
Prof: Sounds like a good example. It’s useful to think about the base case first. Actually, before that, let’s think about a few examples. You had the example with two reposts and a regular post. What else should we test?
Student: Probably a regular post on its own?
Prof: Sounds like a good idea. Let’s get that down with placeholder values as answers.
Student: All right.
Student: Is that what you meant by placeholder values? They return false?
Prof: Right. This makes it so we can run it, and we get the check for errors like making sure we spelled the method correctly everywhere. Now we can fill in the cases. Depending on the problem it can be easier to start with the base case or the recursive case, but for me it’s often that the base case is easier. How do we check if a word is in a post chain that’s just a regular post? Like what should the answer be for hasWorld, and how do we calculate it from word and message?
Student: Hmm I guess we use contains on the string? Like it’d be return
message.contains(word); or something?
Prof: Awesome. We can fill that in. Then we need to think a little bit about the Repost case.
Student: Well it’s like, we check message.contains here, too. Then if the original field is a RegularPost, then we just check that. If the original field is a Repost, then we need to check its message and its original more.
Prof: Let’s try going from the pattern we had before. What does the pattern tell us should show up in the recursive method?
Student: Hmm well I guess… a recursive call?
Prof: And what would that recursive call look like in this case?

Student: I guess like… hmm.. like original.hasWord(word). So the pattern is like

boolean hasWord(String word) { ... message ... original.hasWord(word) ... }
Prof: Right! And what does that recursive call tell you? Describe it.
Student: It’s, I guess a boolean. And it always returns false right now.
Prof: Ah, right, so this is important. When we write a recursive method, we need to trust ourselves a little bit. Say we trust ourselves that hasWord is going to be implemented perfectly. Then what does the return value of original.hasWord mean?
Student: It’s whether the word appears in the original’s message. Oh wait, no, whether it appears in the whole chain starting at original?
Prof: Indeed! And then we need to combine that information with information about this Repost. The word appears if it appears in either the message of this Repost or in the chain that starts with original.
Student: So I combine them with || to get the answer?
Prof: Try it!
Student: Whoa, that worked.
Prof: Pretty cool, right?

Practice

Exercise 1. Fill in totalMessageLength, which adds up the lengths of all the messages in a chain of posts. A String’s length() method gives its number of characters. Hint: in the recursive case, combine this post’s part and the answer of the recursive call with +.

interface Post {
int totalMessageLength();
}
record Repost(String message, Post original) implements Post {
public int totalMessageLength() {
return ;
}
}
record RegularPost(String message) implements Post {
public int totalMessageLength() {
return ;
}
}
Post reg = new RegularPost("Hello world!");
Post r = new Repost("what he said",
new Repost("what she said",
new RegularPost("I love to post")));
int regTotal = reg.totalMessageLength();
int rTotal = r.totalMessageLength();

Exercise 2. Fill in oldestKnownGeneration, which says how many generations back a family tree goes before it runs out of known people. An Unknown goes back 0 generations. A Known whose parents are both Unknown goes back 1: just that person. Hint: Math.max(a, b) gives the larger of two ints, and a Known has two parents to ask.

interface Ancestor {
int oldestKnownGeneration();
}
record Known(String name, Ancestor parent1, Ancestor parent2) implements Ancestor {
public int oldestKnownGeneration() {
return ;
}
}
record Unknown() implements Ancestor {
public int oldestKnownGeneration() {
return ;
}
}
Ancestor pat = new Known("Pat", new Unknown(), new Unknown());
Ancestor lee = new Known("Lee", new Unknown(), new Unknown());
Ancestor kim = new Known("Kim", lee, new Unknown());
Ancestor sam = new Known("Sam", pat, kim);
int samGenerations = sam.oldestKnownGeneration();