☰ Contents Recursive Data

Tracing Recursive Methods

Student: So we wrote this hasWord method recursively, that’s great. How would it work on, like, a really big chain of posts? I feel like I’m not totally clear on how it runs.
Prof: That’s a great question. Let’s first look at a memory trace for the call to r.hasWord("post") to see a small case, then we can think about generalizing to bigger ones.
Names (the stack), over time →
top level
reg = @1002
r = @1008
hasPost = true
r.hasWord("post") on @1008
word = @1009
returns (false || true) → true
message.contains(word) on @1003
s = @1009
returns false
original.hasWord(word) on @1007
word = @1009
returns (false || true) → true
message.contains(word) on @1004
s = @1009
returns false
original.hasWord(word) on @1006
word = @1009
returns true
message.contains(word) on @1005
s = @1009
returns true
Heap
@1001: "Hello world!"
@1002: RegularPost[message=@1001]
@1003: "what he said"
@1004: "what she said"
@1005: "I love to post"
@1006: RegularPost[message=@1005]
@1007: Repost[message=@1004, original=@1006]
@1008: Repost[message=@1003, original=@1007]
@1009: "post"
Prof: So, notice there’s a moment where we have three active calls to hasWord. Two of them have receivers that are Repost instances, and one is a RegularPost instance (at the top). The stack “builds up” this computation, and then we’ll get a true from the topmost stack frame. We’ll then “unwind” through all the frames, returning true, using || to combine it with the false values that came back from the other calls to message.contains, and then finally result in true. In this example, I drew the strings on the heap, so you can see the receivers given to the contains method.
Student: OK, I think I get it. So in false || true, the false is coming from message.contains and the true is coming from the recursive call?
Prof: Good observation. That’s right. Do you think that will always be the case, or is that specific to this example?
Student: Hmmm, well the next example looks for "said", which is true on the first of the Repost instances. So there would be a true on the left, right?
Prof: Great question, let’s trace that one.
Names (the stack), over time →
top level
reg = @1002
r = @1008
hasSaid = true
r.hasWord("said") on @1008
word = @1009
returns true || original.hasWord(word) → true
message.contains(word) on @1003
s = @1009
returns true
Heap
@1001: "Hello world!"
@1002: RegularPost[message=@1001]
@1003: "what he said"
@1004: "what she said"
@1005: "I love to post"
@1006: RegularPost[message=@1005]
@1007: Repost[message=@1004, original=@1006]
@1008: Repost[message=@1003, original=@1007]
@1009: "said"
Student: Wait, where are all the recursive calls?
Prof: In this case, it stops after the first message.contains, because if the left value of || is true, the whole || expression stops before evaluating the right hand side. This is called short circuiting.
Student: So even though we wrote a recursive method, it might not actually make recursive calls?
Prof: Right – it’s a search that returns as soon as it finds a match, and might never actually look at original. But it will make the recursive call if it needs to. Can you think of an example input that would make one recursive call on r, but not two?
Student: Hmmm so it would have to match at the second repost but not the first… "she"?
Prof: Right! OK now back to your original question. What if there were hundreds of Repost instances in a chain, and we searched for a word that only appeared in the innermost RegularPost. What would the memory diagram look like?
Student: Hmmm so it would have lots and lots of frames at once all with Repost receivers, and then one at the very top that is a RegularPost? Like our first picture, but way more frames.
Names (the stack)
message.contains(word)
s = post
returns true
original.hasWord(word) on @1001
word = post
original.hasWord(word) on @1002
word = post
⋮ 297 more original.hasWord(word) frames, each on a Repost
original.hasWord(word) on @1300
word = post
r.hasWord("post") on @1301
word = post
top level
r = @1301
Heap
@1001: RegularPost[message=I love to post]
@1002: Repost[message=lol, original=@1001]
@1300: Repost[message=lol, original=…]
@1301: Repost[message=lol, original=@1300]
Prof: That’s a great sketch, and it is indeed what the stack looks like for very “deep” recursive calls.

Practice

Here is totalMessageLength from the last step, called on the chain from before. The lengths of the three messages are in the chart, and the values returned by totalMessageLength are left out.

Post r = new Repost("what he said",
          new Repost("what she said",
            new RegularPost("I love to post")));
int total = r.totalMessageLength();
Names (the stack), over time →
top level
r = @1006
total = ???
r.totalMessageLength() on @1006
returns ???
message.length() on @1001
returns 12
original.totalMessageLength() on @1005
returns ???
message.length() on @1002
returns 13
original.totalMessageLength() on @1004
returns ???
message.length() on @1003
returns 14
Heap
@1001: "what he said"
@1002: "what she said"
@1003: "I love to post"
@1004: RegularPost[message=@1003]
@1005: Repost[message=@1002, original=@1004]
@1006: Repost[message=@1001, original=@1005]
Fill in what each call of totalMessageLength returns.
original.totalMessageLength() on @1004 returns
original.totalMessageLength() on @1005 returns 13 + →
r.totalMessageLength() on @1006 returns 12 + →