# More recursion; public/private pairs

## Problem solving

Now that we’ve seen a number of templates and examples of recursive programs, let’s practice writing our own recursive programs.

Outline for solving recursion problems
1. Identify one or more base cases.
2. Decompose the problem into one or more smaller, independent subproblems.
3. Combine the results of the smaller subproblem(s) into a final solution.

Base cases are often the simplest valid inputs to the problem. For problems involving integers, base cases are typically 0, 1, single-digit values, or negative numbers. For problems involving arrays, one base case is typically the empty array (though with a caveat that we’ll point out later).

Let’s implement a method, `skipAdd`, that takes a non-negative integer `n` and returns the sum of every other integer between 0 and `n`. For example, `skipAdd(5)` should return 5 + 3 + 1 + 0 = 9 while `skipAdd(4)` should return 4 + 2 + 0 = 6.

Outline how to solve skipAdd following the steps above.
1. The simplest valid input to the problem is 0, the smallest non-negative integer. We know `skipAdd(0)` should return 0.
2. A larger problem like `skipAdd(4)` relies on calling `skipAdd(2)` which then calls `skipAdd(0)`. Each recursive call is passed the input `n - 2`.
3. If we want to solve `skipAdd(4)`, the recursive call to `skipAdd(2)` returns 2. In order to return the final solution, 6, we need to add `4`. In general, we’ll want to add `n`.

Turning the outline into code might look something like the following.

``````// pre : n >= 0
// post: Returns the sum of every other integer between 0 and n
public static int skipAdd(int n) {
if (n == 0) {
return 0;
} else {
return n + skipAdd(n - 2);
}
}
``````

We can check our work by examining the domain of the method and its recursive subproblems. The domain of a function is all of the possible values of its inputs (parameters). `skipAdd(n)` depends on `skipAdd(n - 2)` to work correctly. Our overall recursive approach seems reasonable based on the mathematical formula from our outline, but we’ll want to double check the complete domain. For this problem, since we’re subtracting by 2, even and odd input integers will matter. For example, `skipAdd(5)` will call `skipAdd(3)`, `skipAdd(1)`, `skipAdd(-1)`, … forever! (In reality, Java will throw a `StackOverflowException` once it detects that there are too many recursive calls.)

There are multiple ways of addressing this problem. One way is to introduce a second base case.

``````// pre : n >= 0
// post: Returns the sum of every other integer between 0 and n
public static int skipAdd(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return n + skipAdd(n - 2);
}
}
``````

It would also work to combine these two base cases.

``````// pre : n >= 0
// post: Returns the sum of every other integer between 0 and n
public static int skipAdd(int n) {
if (n == 0 || n == 1) {
return n;
} else {
return n + skipAdd(n - 2);
}
}
``````

Real world problems can involve multiple variables that interact in different ways, so identifying the simplest base cases won’t always be straightforward. It can be helpful in these scenarios to instead focus first on identifying how larger inputs should be decomposed, and then using the relationships between the original problem and the recursive subproblems to help identify more complicated base cases.

## Array sum

Let’s implement a method `sum` that takes an `int[]` and returns the sum of the values in the array. We’ve seen a couple ways to do this iteratively in this course using either regular loops or the for-each loop (iterators).

``````public static int sum(int[] data) {
int total = 0;
for (int i = 0; i < data.length; i++) {
total += data[i];
}
}
``````
Outline how to solve sum.
1. The simplest valid input to the problem is an empty `data` array.
2. A subproblem for `[1, 2]` could be the rest of the `data`: ``. Since we’re breaking down the problem by looking at one less element, we only need to include one base case for the empty `data` array.
3. Since the `sum()` is just 2, we can add the value at `data` to arrive at the final solution.

It turns out that there are some interesting hiccups with turning this outline into code. The following code does not work!

``````public static int sum(int[] data) {
if (data.length == 0) {
return 0;
} else {
return data + sum(data);
}
}
``````
Why doesn't this recursive method work?

In our outline’s recursive case, we wanted to break down the problem by reducing the `data` by one element. Here, we’re not changing the `data` array when we pass it to the next recursive call. So the program will continue recursing on the original `data` array!

One way to address this is to make a new array with all but the zeroth element of `data`. However, this is very inefficient since each recursive call needs to make a new array of length `data.length - 1`.

Comparing the iterative implementation to the recursive implementation can point us towards a solution. The iterative implementation keeps track of an integer index `i`. Each iteration of the loop processes the element at `data[i]`. How might we convert this idea to recursion, such that each recursive call processes the element at `data[i]`?

An initial (but incorrect) approach could be to introduce an index `i` as a local variable.

``````public static int sum(int[] data) {
if (data.length == 0) {
return 0;
} else {
int i = 0;
int value = data[i];
i++;
return value + sum(data);
}
}
``````

## Public/private pairs

In a recursive implementation of `sum`, each recursive call to `sum` gets its own parameters and local variables. These parameters aren’t shared between calls!

In Java, we share information between recursive calls by passing the data in as parameters. To maintain a simple `public` interface, we’ll keep the `public` method header the same but move all of the recursive code into a `private` “helper” method with the variables that we want to change between recursive calls.

``````public static int sum(int[] data) {
return sum(data, 0);
}

private static int sum(int[] data, int i) {
if (data.length == i) {
return 0;
} else {
return data[i] + sum(data, i + 1);
}
}
``````

The role of the `public` method is to start off the recursive process by calling the recursive `private` helper method. Each recursive call to the helper method processes the element at `data[i]` before making a recursive call for the sum of the remaining elements. Note that we also changed the base case to correspond with `i` reaching the end of `data.length`.

The advantage of introducing this public/private pair is that the client does not need to know any of the implementation details or setup any of the recursive variables. This also lets the implementer change their implementation however they want by introducing new variables without breaking client code.

Alternatively, it’s also possible to share information by storing the variable as a field in the instance. However, this can lead to buggy code since fields are permanent parts of an object and might need to be reset, i.e. each new call to `sum` needs to start `i` at 0.

## Tree recursion

So far, all of our recursive programs haven’t really benefited from recursion since simple iterative solutions exist. However, there are some problems that are much more well-suited for recursion. We’ll turn our attention to how Java evaluates tree recursion, recursive programs that make more than one recursive call, resulting in a tree-like series of calls. We’ll learn how to write our own tree recursive methods in later lessons. Today, our focus is on understanding how Java evaluates them.

Let’s see how tree recursion works in the context of a subtraction game. In game theory, a subtraction game is a simple game with two players. At the beginning, there is a pile of `n` cookies. The players alternate turns. Each turn, a player can take either 1 or 2 cookies. The player who takes the last cookie wins. We’ll assume that each player takes the optimal number of cookies to win the game. For example, if there are three cookies in the pile and it’s our turn, we can’t win the game.

1. If we take 1 cookie, the other player can take 2 cookies and win the game.
2. If we take 2 cookies, the other player can take 1 cookie and win the game.

Let’s consider the `canWin` method, which returns true when it is possible to win if it’s our turn and there are `n` cookies in the pile. The method works by simulating each player taking successive turns, so we win if we put the other player in a situation where they’re guaranteed to lose `!canWin`.

``````public static boolean canWin(int n) {
if (n == 0) {
return false;
} else if (n == 1) {
// Take 1 cookie to win the game
return true;
} else {
// Is the other player forced to lose?
boolean takeOne = !canWin(n - 1);
boolean takeTwo = !canWin(n - 2);
return takeOne || takeTwo;
}
}
``````

Simulating the code, we get the following trace for `canWin(3)`. (Our human prediction is outlined above.) We start with 3 cookies on the pile by playing `canWin(3)`.

1. We take 1, so they will be playing `canWin(2)`.
1. They take 1, so we will be playing `canWin(1)`. We win!
2. They take 2, so we will be playing `canWin(0)`. We lose!
3. `return` they can win if we take 1 since there’s a position where they win (and we lose).
2. We take 2, so they will be playing `canWin(1)`. They win!
1. `return` they can win if we take 2 since there’s a position where they win (and we lose).
3. `return` we lose since there are no positions where we can win.

In this simple game, there are many winning positions so long as we avoid leaving either 0 or 3 cookies on the pile. However, this same idea applies to many more complicated problems, such as artificial intelligence for playing chess and simulation of protein folding for biomedical applications. These real-world problems are much harder for even supercomputers to solve for two reasons.

1. The number of options to explore is exponential with respect to the size of `n`. Even simulating all of the possible playthroughs for `canWin(1000)` can take a long time. Imagine the time it takes to compute `n` in the millions or billions!
2. Rather than only two options (take 1 or 2 cookies), there are dozens, hundreds, or even more options to consider at each turn.