Recursion - Building Java Programs: A Back to Basics Approach - page 747

The key to the iterative approach is to work with an index variable that starts at 0
and continues iterating until it equals the length of the array. We can apply this same
idea to a recursive solution. Remember that you want to think about how to pick off
some small piece of the problem. Consider the following line of pseudocode:
sum(entire list) = list[0] + sum(list starting at 1)
This code states that we have to add in list[0] . That leaves us with the task of
adding up the remaining values of the list (the values starting at index 1). And how
would we do that? We can similarly say that:
sum(list starting at 1) = list[1] + sum(list starting at 2)
This approach leads to a series of recursive calls, each of which handles one ele-
ment of the array:
sum(entire list) = list[0] + sum(list starting at 1)
sum(list starting at 1) = list[1] + sum(list starting at 2)
sum(list starting at 2) = list[2] + sum(list starting at 3)
...
When does this process end? We could end when we get to the last element of the
array:
sum(list starting at list.length - 1) = list[list.length - 1]
Unfortunately, this choice of ending point assumes that a last element exists. That
won't be true of an array of length 0. An easier approach is to end when we reach an
index beyond the last element of the array. The for loop version of this method exe-
cutes for as long as the index is less than the length of the array. Once the index
becomes equal to the length of the array, it stops. Our recursion can similarly stop
when the index becomes equal to the length of the array. And what does that add up
to? It adds up to 0:
sum(list starting at list.length) = 0
Returning 0 in this case is the recursive equivalent of initializing the cumulative
sum to 0.
We are almost ready to write the recursive method, but to express this idea as a
method, we have to pass the method both the array and the starting index. So we
want our method to look like the following:
// computes the sum of the list starting at the given index
public int sum(int[] list, int index) {
...
}