Recur on A[0 ... n - 2] , add the result to A[n - 1] , then return the sum

Question

Write a recursive function called sumArray() that determines the sum of the integers in an array A[0...n-1]. Recur on A[0 ... n-2] , add the result to A[n-1] , then return the sum.

Code:

    static int sum1(int[] A, int p, int r) {
        int r2= r-1;
        if (p==r)
            return p;
        else if(p==r2) 
           return A[r2]+A[p];
        else
           p=sum1(A,p+1,r2)+p;
        return p+A[r];
   }

The array A I'm inputting is int[] A = {1,2,3,4,5,6,7,8,9,10} which leads to a value of 50, not 55. What is wrong with my code?

Possible duplicate of [Java : Testing Array Sum Algorithm Efficiency](https://stackoverflow.com/questions/37233061/java-testing-array-sum-algorithm-efficiency). The second function in the question is the one you're looking for. — Prune, Jul 13 '17 at 16:18

Davide Spataro · Answer 1 · 2017-07-12T17:55:51.050

1

The same logic can be written in a much cleaner way as follows:

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

and you call it with p always equals to size(A)-1:

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

Note that you can compute a recursive sum of A withouth modifying it as follows (same logic as before, without updating A)

Here is the code:

static int sum1(int[] A, int p) {
    if (p < 0) return 0;
    return A[p]+sum1(A, p - 1);
}

edited Jul 12 '17 at 17:55

answered Jul 12 '17 at 17:49

Davide Spataro

7,319
1
24
36

You do realize this question is about java? And your algorithm alters the array without any need to do so. Logic is correct though. – Jul 12 '17 at 17:50
Java now. Regarding the modification of the array, the question says: add the result to A[n-1] and then return . I assume that A needs to be modified. =) – Davide Spataro Jul 12 '17 at 17:52
Maybe I overinterpreted the question. Personally I still think that the algorithm was meant to not alter the array and that the question was poorly worded. At least OPs algorithm doesn't alter the array. – Jul 12 '17 at 17:54
added a version which simply computes the sum recursively. – Davide Spataro Jul 12 '17 at 17:57
Yeah I agree the question is worded confusingly. I got it by modifying your code. I was using the index not the actual value. Thanks! – zarasta Jul 12 '17 at 18:39

Recur on A[0 ... n - 2] , add the result to A[n - 1] , then return the sum

1 Answers1