# Recursive Programming

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

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. Since a recursive call to `skipAdd(2)` should return 2, the result of `skipAdd(4)` should be 6 = 4 + `skipAdd(2)`. In general, we compute the complete result by adding the value of `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 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.

Give an example input to skipAdd that will reveal a problem.

Since we’re subtracting by 2, even inputs might do different things when compared to odd inputs. For example, `skipAdd(5)` will call `skipAdd(3)`, which will call `skipAdd(1)`, `skipAdd(-1)`, `skipAdd(-3)`, … forever! It’s like we’ve defined a `while` loop that continues forever because the loop condition is never false.

In reality, Java will throw a `StackOverflowException` and stop the program once it detects that there are too many recursive calls.

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];
}
}
``````
Describe an outline for a recursive sum algorithm.
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.

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);
}
}
``````
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!

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.