Recursion algorithm for the sum of all elements in a list in java

you have to remove the last element

public static int countNumberOfElements(int[] elements) {
    int count = elements.length;
    if (elements.length == 0) {
        return 0;
    } else {
        int newArray[] = Arrays.copyOf(elements, count - 1);
        return (countNumberOfElements(newArray) + elements[count - 1]);
    }
}

Try something like this.

 int getSum(int[] items){
    return getSum(items, items.length - 1, 0);
 }

 int getSum(int[] items, int index, int sum){
    return index < 0 ? sum: getSum(items, index - 1, sum + items[index]);
 }

You could try:

static int findSum(int A[], int N){
    if (N <= 0)
        return 0;
    return (findSum(A, N - 1) + A[N - 1]);
}

where A is the array and N is the length of the array.

P.S. you mention a list in your question and then use and array in your example so I'm assuming you mean array 👍

You can create separate recursive method and call it from your method:

public int countNumberOfElements(int[] elements) {
    if (elements.length == 0)
        return 0;
    else
        return countNumberOfElementsRec(elements, 0);
}

public int countNumberOfElementsRec(int[] elements, int index) {
    if (index >= elements.length)
        return 0;
    else
        return elements[index] + countNumberOfElementsRec(elements, index + 1);
}

Whittling the problem down element by element can result in stack overflow for even moderate sized arrays. This can be avoided by adding range values first and last to the recursive method's argument list and splitting the resulting range (roughly) in half to generate two sub-ranges which differ by no more than 1 in length. Recursively apply this splitting process on each sub-range until you get down to ranges containing a single element, whose "sum" is the value of that element. Then sum the results of the recursive calls and keep passing the cumulative results back up the recursion tree. The repeated halving reduces the number of recursive calls to O(log(elements.length)) rather than O(elements.length). The recurrence for the running time is T(n) = 2T(n/2) + O(1) => O(n), so this approach (like the solutions proposed by others) calculates the sum in linear time.

I have broken the implementation into a public front-end which takes the array as its sole argument, and a separate private recursion which has additional arguments for the range info. This hides the range bookkeeping from the end user. This is a common and useful trick when the recursion requires info which can be derived from the data itself, or involves value or type checking which only needs to be performed once up-front. Separating those derivations and checks into a front-end reduces the amount of work done in the recursive calls and makes the public facing method interface more user friendly. I've also made the return type long, because the sum of two ints can overflow the capacity of an int. The following code:

class Test {

    // Public facing front end
    public static long sumArray(int [] elements){
        int count = elements.length;
        if (count == 0) {
            return 0L;
        } else {
            return _sumArray_(elements, 0, count - 1);
        }
    }

    // Private recursive worker-bee to do the actual task.
    private static long _sumArray_(int [] elts, int first, int last) {
        // When focus is on a single element, return its value
        if (last == first) {
            return (long) elts[first];
        }
        // Otherwise find the mid-range index for the current range
        int mid = first + (last - first) / 2;
        // Sum the sums of the two resulting sub-ranges
        return _sumArray_(elts, first, mid) + _sumArray_(elts, mid + 1, last);
    }

    public static void main(String[] args) {
        int [] ary = {5,6,7,1,2,3,4,8,9,10};
        System.out.println(sumArray(ary));
    }
}

produces the correct answer of 55 for the test data provided in main.

To summarize, this solution:

• yields correct answers, even if the array contains very large int values (returns long to avoid integer overflow);
  • Example: processing int [] ary = {2147483647,2147483647}; with methods which return int will yield -2 rather than the correct answer of 4294967294
• doesn't require the end-user to remember and supply other arguments in addition to the data itself;
• matches the time complexity of other proposed solutions; and
• dominates all of the other solutions on the size of the recursive stack, so it won't cause stack overflows if you use it for arrays containing hundreds of thousands of elements or more.
  • Example: methods which divide a problem of size n into subproblems of size 1 and n-1 will generate a java.lang.StackOverflowError on large arrays such as int [] ary = new int[100000]; java.util.Arrays.fill(ary, 42);, while splitting the problem in successive halves handles an array with 100M elements with no problems.