☰ Contents Recursive Data

A Universal Base Case

Student: My friend figured out how to make recursive data without an interface.
Prof: Oh really?
Student: Well, actually it was AI again. But I was trying to figure out some of this recursive data stuff, and it made a program that had null in it:
Student: It looks like it uses null everywhere we would have had a base case like Unknown.
Prof: Ah I see. Yes, you can do this! Java will let you store null in a field or variable or parameter of any reference type. So null can be stored in a Person field.
Student: So why don’t we just use that all the time?
Prof: You can, but it requires using a different style. The main reason is I like having the base case classes to put methods in. For example, if we want to have a oldestKnownGeneration method, how do we do that? Try to write it inside Person.
Student: Ummm, let’s see, we need to check if either parent is null right? And if they are, then we return 1, because there’s nothing more to visit.
Student: Wait, why is that an error?
Prof: Let’s look at the trace
Names (the stack), over time →
top level
p = @1002
p.oldestKnownGeneration() on @1002
throws NullPointerException: parent2 is null
parent1.oldestKnownGeneration() on @1001
returns 1
Heap
@1001: Person[name=Brenda, parent1=null, parent2=null]
@1002: Person[name=Bob, parent1=@1001, parent2=null]

Prof: On the person with name "Bob", there’s one parent that’s null and another that isn’t. So we try to call parent2.oldestKnownGeneration(), but parent2 is null. That is exactly what NullPointerException means: trying to use a field or call a method on the value null.

So we’d actually need two checks – one for each parent. Those would be some number, or 0 if null. In my opinion, the code for this gets pretty complex:

Student: Huh. How did you know to do both of those checks?
Prof: Lots of experience. It’s not clear to me in all cases how to structure this code. I find the structural definition works better. Plus, this example had a clear “empty” case – when the ancestor is unknown. In other cases, like your Post, the base case actually has information in it, like the message of a RegularPost.
Student: Hmm, OK. So sometimes we can use null for base cases?
Prof: I think you can, but it’s not clear how often you should. And NullPointerException is not a fun one to get. My advice is to try to write null-free programs! And if you see null come up in a recursive program you’re reading, try to think of it like a base case class.
Student: Huh. I’ll think about that.

Practice

Here is another method on the same Person record, which counts the known people in a family tree. It checks parent1 for null, but not parent2.

record Person(String name, Person parent1, Person parent2) {
  int countKnown() {
    int count = 1;
    if(parent1 != null) { count += parent1.countKnown(); }
    count += parent2.countKnown();
    return count;
  }
}
Person ana = new Person("Ana", new Person("Ben", null, null), new Person("Cy", null, null));
int known = ana.countKnown();
Running this crashes with a NullPointerException. Where does it happen?
  1. At parent2.countKnown(), in the call on Ben
    ana.countKnown() first asks Ben. Ben’s parent1 is null, so the if skips it, but his parent2 is null too, and nothing checks it.
  2. At parent2.countKnown(), in the call on Ana
    Ana’s parent2 is Cy, who is not null. And the program never gets that far: it crashes while Ana is still waiting for her parent1′s answer.
  3. At parent1.countKnown(), in the call on Ana
    Ana’s parent1 is Ben, who is not null, so this call starts, and it is the call on Ben that crashes.
  4. At parent1.countKnown(), in the call on Ben
    Ben’s parent1 is null, but the if checks it first, so this call never runs.
How many calls of countKnown start before the program crashes?