Link Menu Search Expand Document
CSE 143

More recursion; public/private pairs

ed Lesson

Table of contents

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];
    }
    return total;
}
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: [2]. 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([2]) is just 2, we can add the value at data[0] 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[0] + 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.