Recursive Programming

Table of contents

1. Problem solving
2. Array sum
3. Public/private pairs

Problem solving

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

Outline for defining recursive algorithms

1. Identify one or more base cases.
2. Decompose the problem into one or more smaller, independent subproblems.
3. Combine the result of each subproblem to compute the complete result.

Base cases represent the smallest or simplest valid inputs to the algorithm. For problems involving integers, base cases are typically 0, 1, single-digit values, or negative numbers. For problems involving data structures, a common base case is an empty collection (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.

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 verifying the result of each recursive subproblem. 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.

There are multiple ways of addressing this problem.

1. 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);
       }
   }
   

2. Another way would be 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 often involve several parameters that interact in different ways, so identifying the simplest base cases won’t always be straightforward. Don’t be afraid to add more base cases than necessary when starting out! Studying the relationships between more examples by writing them down is an effective strategy for identifying the relationships between recursive subproblems.

Array sum

Let’s implement a recursive method sum that takes an int[] and returns the sum of the values in the array. We can solve this problem iteratively by keeping track of a counter variable for the index i and summing the result so far with total.

public static int sum(int[] data) {
    int total = 0;
    for (int i = 0; i < data.length; i++) {
        total += data[i];
    }
    return total;
}

There are several details that Java programmers need to be careful about when 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);
    }
}

Studying the iterative implementation can point us to a solution. The iterative implementation keeps track of an index i. Each iteration of the loop processes the element at data[i]. How might we represent this idea in a recursive algorithm?

An initial (but incorrect) approach to be to introduce an index i as a local variable. Each recursive call to sum gets its own parameters and local variables. These parameters aren’t shared between recursive calls!

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

All of these recursive sum algorithms share a common constraint: the domain is defined by a single parameter, data.

int sum(int[] data)

Each subproblem is defined solely by data.

Given the same data array as input, the method should always produce the same outcome. This makes it tricky to represent different subproblems without constructing new arrays. Let’s change the domain of the method to workaround this constraint.

int sum(int[] data, int i)

Each subproblem is defined by the pair of values, data and i.

To maintain a simple public interface, we’ll keep the public method header the same and move all of the recursive code into a private helper method.

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 the recursive process by calling the 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.

Recall that the original iterative approach also maintained a counter variable for the index i. When converting iterative algorithms to recursive algorithms, variables that change between each iteration must be represented as parameters to the recursive algorithm.

Public/private pair

Define a private helper method that accepts a larger domain of parameters.

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.