Lecture 36

Announcements

CS 4730 (game design) is having a game expo Today (18 April) from 2:30–4:30 in Rice 120. Play games, be entered in a door prize drawing, and do it all in the name of academia!

Talking Points

Recursion!

Stack Overflow

public static int sum(int a, int b) {
    return sum(a - 1, b + 1);
}

public void setField(double value) {
    this.setField(value);
}

Activity

1. If asked What's n for some number n:
   1. Stand up
   2. If n ≤ 0, reply 1 to whoever asked you the question.
   3. Otherwise,
      1. Find two sitting people.
      2. Ask one What's n − 1 and the other What's n − 2.
      3. Add together whatever they reply.
      4. Reply with that sum to whoever asked you the question.
   4. Sit down

Activation Records

In this activity, standing people are activation records, and sitting people are unused memory. Each activation record needs to remember:

1. Its parameters' values
2. Its local variables' values
3. Who it is waiting for
4. Where it will resume in the code when the one it is waiting for finishes

Java does not let a method wait for two other methods at the same time. Instead, java's model is more like

1. If asked What's n for some number n:
   1. Stand up
   2. If n ≤ 0, reply 1 to whoever asked you the question.
   3. Otherwise,
      1. Find a sitting person and ask them What's n − 1; remember their reply.
      2. Once the first person responds, find a sitting person and ask them What's n − 2; remember their reply.
      3. Add together the two replies you remembered.
      4. Reply with that sum to whoever asked you the question.
   4. Sit down

This model has the advantage of making the find a sitting person step very easy: you line everyone up and each person always asks the next person in line every time.