Consider the problem of calculating the sum of the elements in a 1D int array. A method to do this would be expected to accept the array as a parameter and return an int.

public static int sum(int[] arr)

The method could be called as:

int[] vals = {3, 8, 4, 6};
System.out.println(sum(vals)); // 21

Ridiculous recursive implementation

The method can be implemented recursively. (Obviously, the method can also be implemented with a simple loop.)

public static int sum(int[] arr)
{
    if(arr.length == 0)
        return 0;
    
    int[] shorterArr = new int[arr.length - 1];
    for(int i = 0; i < shorterArr.length; i++)
        shorterArr[i] = arr[i];
    
    return sum(shorterArr) + arr[arr.length - 1];
}

This recursive solution is ridiculous. It is ridiculous not because it is recursive, but because it makes a new array during each step of the recursion.

The method header is the issue. Since the method accepts only an array, the base case must be written in terms of the length of the array. Approaching the base case requires making, and filling, a shorter array.

Appropriate recursive implementation

Consider the modified method header below.

// returns the sum of arr[startIndex] ... arr[arr.length - 1]
public static int sum(int[] arr, int startIndex)

As the comment indicates, the updated method returns the sum of the values in arr from startIndex to the end.

This modified method can be implemented recursively.

public static int sum(int[] arr, int startIndex)
{
	if(startIndex >= arr.length)
		return 0;
	
	return sum(arr, startIndex + 1) + arr[startIndex];
}

The base case is now in terms of the number of elements in the portion of the array to be summed. Approaching the base case requires specifying a smaller portion of the array. The array itself remains unchanged.

Conversion into a helper method

One issue remains with the modified method header. Client code would call the modified method as:

int[] vals = {3, 8, 4, 6};
System.out.println(sum(vals, 0)); // 21

This works, but is silly. A method to sum the elements in a 1D array should take the array, not the array and a start index.

The original method header is appropriate for a public method. The modified method header is appropriate for a recursive solution. The solution is to write both methods.

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

// returns the sum of arr[startIndex] ... arr[arr.length - 1]
private static int sum(int[] arr, int startIndex)
{
	if(startIndex >= arr.length)
		return 0;
	
	return sum(arr, startIndex + 1) + arr[startIndex];
}

Method sum(int[], int) is a private recursive helper method. Method sum(int[]) calls sum(int[], int).

Helper methods are used for a variety of reasons. Recursive helper methods are often used when the parameters for a public method do not match the parameters desired for a recursive implementation. The public method implementation is often trivial, though this is a not a requirement.

Alternative with artificial length

public static int sum(int[] arr)
{
    return sum(arr, arr.length);
}

// returns the sum of arr[0] ... arr[len - 1]
private static int sum(int[] arr, int len)
{
    if(len == 0)
        return 0;
    
    return sum(arr, len - 1) + arr[len - 1];
}

Some programmers prefer to accept the length of the portion of the array being considered.

Additional practice

The CodingBat exercises array6, array11, and array220 each use the technique above to traverse the array. Each exercise specifies only the recursive helper method (as public).

Comments

Comment on Recursive helper methods