Game

• Ask Player one for a bid.
• Output that bid.
• Set “current” player to Player two.
• As long as….?
  • Ask the current player for their raise.
  • Output the current bid.
  • Change the current player (now it’s the other player’s turn)

Game (Continued)

• Afterward: print out who won!
  • Who made the last bid? (Current player? Or the other one?)
  • Was it correct?

Time Management

• This week:
  • Simple classes: Die, Bid
  • Player interface, RandomPlayer, HumanPlayer
  • Test out that these do exactly what you need.
  • Think about the gameplay while designing these.
  • Start working on the Game class.
• Early next week:
  • Get the gameplay working.
  • Does it figure out the correct winner each time?
  • Test it out with all 3 ways to play.

After that

• Smarter Player
  • As you play the game, try to think about strategies that make sense.
  • Can you implement any of those?
  • Can you recognize when you definitely should call LIAR?
  • Can you just find anything better than the Random player?
• Testing! How well does it work? Against you? Against the Random player?
• Then: add menu of all 8 choices.
• Test out all 8 ways of playing.

Example

Starter Code

public static int add(int x, int y) {
    System.out.println("Calling add(" + x + ", " + y + ")");
    if (y == 0) {
        return x;
    }
    if (y > 0) {
        return add(x + 1, y - 1);
    }
    if (y < 0) {
        return add(x - 1, y + 1);
    }
    // this shouldn't happen
    return -1;
}

Base Case

A method which invokes itself is called recursive. The add method invokes itself (as long as \(y \neq 0\)).

Recursive methods have a base case: a condition which leads to an actual answer, rather than recursively calling the same method again.

1. What is the need for a base case?
2. What is the base case in the add method?

Exercise

1. Run the RecursionExample program. What is output?
2. Change the parameters and see what happens.
3. Given any input \(x\) and \(y\), if we invoke add(x, y), how “deep” does the recursion go?

5 minutes to discuss these at your tables. Nominate one person from your room to share.

Recursive Calls

• If we know that a method has been implemented correctly, we don’t need to know how it works, we can just call it and use it.
• Similarly, when we see a recursive call, assume it works! Then we can just use it.
• Important: the assumption is that the recursive call works on smalller inputs.
• Strategy is often to reduce the problem to a smaller problem.

Recursive Factorial

public int recursiveFactorial(int n) {
    if (n <= 0) {
        return 1;
    }

    return n * recursiveFactorial(n - 1);
}

• Assume that recursiveFactorial(n-1) correctly returns \((n-1)!\).
• Then \(n \times\) recursiveFactorial(n-1) is, in fact, equal to \(n!\) (Why?)
• Math analogy: proof by induction.

Exercise

Implement a recursive Fibonacci method. Remember:

• fib(0) should return \(0\)
• fib(1) should return \(1\)
• fib(n) should return fib(n-1) + fib(n-2) if \(n > 1\).
• For the purposes of this method, if \(n < 0\), return \(-1\)

Print After

public static void printAfterRecursion(ArrayList<String> list, int i) {
  if (i == list.size()) {
      return;
  }
  printAfterRecursion(list, i+1);
  System.out.println(list.get(i));
}

• list = [a, b, c, d, e], i = 0?
• What do you think it will output?
• Make a stack diagram.
• What does it output?

Exercise: Sum Digits

Starter code Implement the sumDigits method recursively. Hint: to get the ones digit of a number, use \(num % 10\). To remove the ones digit from the number, use \(num / 10\).

public static int sumDigits(int num) {
    if (num < 0) {
        return sumDigits(-num);
    }
    if (num < 10) {
        return num;
    }
    // implement the rest...
}