Interfaces

• CoinGame:
  • Main class has the “game” code.
  • Make a “play” method which depends on the Player interface.
  • main method then can determine which implementations are used.
  • Good general pattern!
  • Hint for project 3: plan the interfaces you’ll be using early!

Example

On Replit

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\)

Exercise: Sum Digits

Replit Part 2 space 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...
}