Other courses of interest

• PHI 2120 Methods of Reasoning
  • Does not count for math/CS, but toward the “outside math/CS credits”
• Manhattanville:
  • Geometry (prerequisite: Calculus 1)
  • Databases
  • Intro to Data Science
  • Building Computer System Software

Game

• Keep track of whose turn it is (maybe a “current” Player variable)
• As long as there are any stones left:
  • Ask the current player to make a move
  • Output that move
  • Update the “board” based on the move
  • Change the current player (now it’s the other player’s turn)
• Afterward: print out who won!
  • Who took the last stone?

Time Management

• This week:
  • Player interface, SimplePlayer, HumanPlayer
  • Test out that these do exactly what you need.
  • Think about the gameplay while designing these.
  • Do you need more classes to make these work?
  • Start working on the Game class.
• Next week:
  • Get the gameplay working.
  • Does it figure out the correct winner each time?
  • Test it out with all 4 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’re in a “winning position”?
  • If not: can you just find anything better than the Simple player?
• Testing!

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...
}