Recursive Data in Summary — Recursive Data

Which of these data definitions has no base case, so the only way to finish building a value is to pass null?

```
record Post(String message, Post original) {}
```
Every Post needs another Post to be built, and there is no other kind of Post to stop at. The only way to finish is something like new Post("hi", null), with null standing in for the base case.

interface Post {}
record Repost(String message, Post original) implements Post {}
record RegularPost(String message) implements Post {}

new RegularPost("I love to post") holds no other Post, so a chain of Reposts can stop there, with no null needed.

interface Ancestor {}
record Known(String name, Ancestor parent1, Ancestor parent2) implements Ancestor {}
record Unknown() implements Ancestor {}

new Unknown() is an Ancestor with no fields, so a family tree can stop there, on either side, with no null needed.

```
record Course(String name, Course[] prereqs) {}
```
A Course whose prereqs array is empty holds no other Course, so it can be built first, with no null needed. That is the base case.

Fill in firstMessage, which gives the message of the regular post a chain of reposts started from.

interface Post {
String firstMessage();
}
record Repost(String message, Post original) implements Post {
public String firstMessage() {
return ;
}
}
record RegularPost(String message) implements Post {
public String firstMessage() {
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")));
String regFirst = reg.firstMessage();
String rFirst = r.firstMessage();

While r.firstMessage() runs, there is a moment when the stack holds the most calls of firstMessage at once. How many calls of firstMessage are on the stack at that moment?

Here is hasWord again:

// in Repost
public boolean hasWord(String word) { return message.contains(word) || original.hasWord(word); }
// in RegularPost
public boolean hasWord(String word) { return message.contains(word); }

How many calls of hasWord run, in all, for r.hasWord("what")?

Fill in countKnown, which says how many known people are in a family tree.

interface Ancestor {
int countKnown();
}
record Known(String name, Ancestor parent1, Ancestor parent2) implements Ancestor {
public int countKnown() {
return ;
}
}
record Unknown() implements Ancestor {
public int countKnown() {
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 samKnown = sam.countKnown();

Fill in evaluate, which works out an expression when every variable stands for the number x. With x as 2, (4 + 5) - x is 7.

interface Expr {
int evaluate(int x);
}
record Num(int value) implements Expr {
public int evaluate(int x) {
return ;
}
}
record Var(String name) implements Expr {
public int evaluate(int x) {
return ;
}
}
record Plus(Expr left, Expr right) implements Expr {
public int evaluate(int x) {
return ;
}
}
record Minus(Expr left, Expr right) implements Expr {
public int evaluate(int x) {
return ;
}
}
Expr e = new Minus(new Plus(new Num(4), new Num(5)), new Var("x"));
int seven = e.evaluate(2);