Recursion on an array

A method that calls itself is recursive. On an array, each call handles 1 position and then calls itself to handle the positions after it. The array is never copied. An index parameter marks the first position still to handle, and each call passes that index plus 1.

The call that returns without calling itself again is the base case. On an array, the base case is usually the index reaching the end of the array (i == array.length), where no positions are left.

A recursion problem on the APE allows no loops. The practice exam's file says No loops of any form are allowed. The recursive call has to do the repeating that a for, while or do loop would do.

Problems that work from both ends of the array at once use 2 indexes in place of 1; see 2 indexes moving toward each other.

Example: adding up an array

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

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

The base case returns 0, because the sum of no numbers is 0. The recursive case adds the element at i to the sum of everything after it.

Trace it on {4, 7, 2}. Each call waits for the call below it to return, then adds its own element.

3 elements make 4 calls: 1 for each element, plus the base case. The base case and the call stack shows how Java keeps track of the calls that are waiting.

The public method and the helper

A caller wants to pass only the array. The recursion also needs the index. So the work is split between 2 methods with the same name and different parameter lists (overloading).

• The public method takes the array, checks it (for example, throws IllegalArgumentException when it is null), and makes the first call to the helper. That first call gives every helper parameter its starting value.
• The helper, often private, holds the base case and the recursive case.

Read the public method's call to the helper before you write the helper. The starting values tell you which positions are already handled and which are left. A first call can pass an element as the starting answer; that element is then already handled.

Carrying the answer down

The sum helper adds as each call returns. A helper can instead pass a partial answer down to the next call, in an extra parameter (an accumulator). The base case then returns the finished answer.

public static int countNegatives(int[] array) {
    return countNegatives(array, 0, 0);
}

private static int countNegatives(int[] array, int i, int count) {
    if (i == array.length) {
        return count;
    }
    if (array[i] < 0) {
        return countNegatives(array, i + 1, count + 1);
    }
    return countNegatives(array, i + 1, count);
}

On {-3, 8, -1} the calls receive a count of 0, 1, 1 and 2. The base case returns 2.

2 indexes moving toward each other

Some problems work from both ends of the array at once. The helper takes 2 indexes: left starts at 0 and right starts at array.length - 1. Each call handles the pair at left and right, then calls itself with left + 1 and right - 1.

This method counts the pairs, 1 from each end, that add up to target.

public static int pairsAddingTo(int[] array, int target) {
    return pairsAddingTo(array, target, 0, array.length - 1);
}

private static int pairsAddingTo(int[] array, int target, int left, int right) {
    if (left >= right) {
        return 0;
    }
    int found = 0;
    if (array[left] + array[right] == target) {
        found = 1;
    }
    return found + pairsAddingTo(array, target, left + 1, right - 1);
}

The base case is left >= right. It covers both ways the indexes can finish.

A base case of left == right catches only the odd case. On an even length the indexes skip past each other, the calls keep going, and an index runs off the array with ArrayIndexOutOfBoundsException.

In the practice APE

Practice exam 1 has 2 recursion problems, findLargest and reverseArray, in its Recursion folder. Practice exam 2 has findLargest and isPalindrome, in src/recursion. In each file the public method is given, and its last line is the first call to the helper you write. Read that call first. Your code goes between the //startMethod and //endMethod lines, and the practice grader checks that the method there calls itself and uses no for, while or do loop. Each findLargest file also says Failure to productively use recursion to solve this problem will result in 0 points.

Readiness check

Work each one on paper and write the answer down before you open the answers.

public static int countAbove(int[] array, int limit) {
    return countAbove(array, limit, array.length - 1);
}