Divide and conquer algorithm for sum of integer array

Question

I'm having a bit of trouble with divide and conquer algorithms and was looking for some help. I am attempting to write a function called sumArray that computes the sum of an array of integers.

This function must be done by dividing the array in half and performing recursive calls on each half. I have tried to use similar concepts to those I employed when writing recursive sum algorithms and a divide and conquer algorithm for identifying the maximum element in an array, but I am struggling to combine the two ideas.

Below is the code I have written for sumArray, which compiles, but does not return the correct result.

int sumArray(int anArray[], int size)
{
    int total = 0;
    //base case
    if (size == 0)
    {
        return 0;
    }
    else if (size == 1)
    {
        return anArray[0];
    }

    //divide and conquer
    int mid = size / 2;
    int lsum = anArray [mid] + sumArray(anArray, --mid);
    int rsize = size - mid;
    int rsum = anArray[size - mid] + sumArray(anArray + mid, --rsize);
    return lsum + rsum;
}

I have identified the problem as being that the function includes the value of lsum in its calculation of rsum. I know the issue lies within my recursive call to sumArray using rsize ( a variable that is equal to the size of the original array, minus the midpoint). For some reason, however, I cannot seem to identify a fix.

I feel silly asking, as I know the answer is staring me right in the face, but how do I repair my function so that it returns an accurate result?

UPDATE: Thanks to all the helpful responses, I have fixed my code and so that it compiles and runs nicely. I will leave my original code here in case others are struggling with divide and conquer and might be making similar mistakes. For a function that correctly solves the problem, see @Laura M's answer. The response by @haris also gives a good explanation of where my code was incurring errors.

Answer 1

int sumArray(int anArray[], int size)
{
    //base case
    if (size == 0)
    {
        return 0;
    }
    else if (size == 1)
    {
        return anArray[0];
    }

    //divide and conquer
    int mid = size / 2;
    int rsize = size - mid;
    int lsum = sumArray(anArray, mid);
    int rsum = sumArray(anArray + mid, rsize);
    return lsum + rsum;
}

Answer 2

In your code:

int mid = size / 2;
int lsum = anArray [mid] + sumArray(anArray, --mid);
int rsize = size - mid;
int rsum = anArray[size - mid] + sumArray(anArray + mid, --rsize);

we can illustrate the error with an example where the array is { 2, 3, 4, 5, 6, 9} and size = 6.

now when you do mid = size / 2, followed by:

int lsum = anArray [mid] + sumArray(anArray, --mid);
int rsize = size - mid;
int rsum = anArray[size - mid] + sumArray(anArray + mid, --rsize);

the number 5 gets added twice (once in lsum and then in rsum) because mid == (size - mid).

Furthermore, the call for sumArray() in rsum should have parameters sumArray(anArray + (mid + 1), --rsize) as element mid has already been added in lsum

On a different note, you can go for a much simpler code for recursion, something like..

int add(int low,int high,int *a)
{
    int mid;
    if(high==low)
        return a[low];
    mid=(low+high)/2;
    return add(low,mid,a)+add(mid+1,high,a);
}

Answer 3

int sumArray(int anArray[],int start,int end){
     if(start==end)
        return anArray[start];
     if(start<end){
         int mid=(start+end)/2;
         int lsum=sumArray(anArray,start,mid-1);
         int rsum=sumArray(anArray,mid+1,end);
         return lsum+rsum+anArray[mid];

     }
     return 0;

}

Answer 4

As haris has said, in your code you add the same number to both the right sum and the left sum; however, there is a much greater problem with your code.

You always pass the same array to your recursive calls for lsum and rsum. At first I thought that was just part of your implementation and that it would be taken care of by the size parameter. However, the size parameter appears to not work as you might have intended it to work. All your algorithm does is reduce the size parameter until it reaches a 1. Then, the base case is triggered, and as a result the first item in the original array always is returned. Why? You never break up the array in your code and so the same array persists throughout each recursive call (even at the base case).

To fix this problem, all sumarray() should do is split the array into a left half and a right half based on the mid calculation and recursively pass this new array until the size of the array is 1 (the base case) and you return the item in the array. This effectively breaks the array into its individual elements, and all the function has to do at this point is add up lsum and rsum.

Pseudocode:

sumArray(array[]){
    if size(array) is 1
          return array[0]

    mid = size(array) / 2 
    leftArray = splitArrayUpto(mid, array)
    rightArray = splitArrayAfter(mid+1, array)

    leftArraySum = sumArray(leftArray)
    rightArraySum = sumArray(rightArray)

    return leftArraySum + rightArraySum
 }   

Answer 5

#include<iostream>
using namespace std;
int sum(int a[], int l, int r)
{
    if(l==r) return a[l];
    int mid = (l+r)/2;
    int lsum = sum(a,l,mid);
    int rsum = sum(a,mid+1,r);
    return lsum+rsum;
}

int main() {
    int b[] = {9,7,2,6,5,3};
    int fsum = sum(b,0,5);
    cout<<fsum;
    return 0;
}

Answer 6

int a[mx], tree[mx*3];

void sum(int node, int s, int e){
  if(s == e)
  {
     tree[node] = a[s];
     return;
  }

  int left = node*2;
  int right = node*2 + 1;
  int mid = (s+e)/2;

  sum(left, s, mid);
  sum(right, mid+1, e);

  tree[node] = tree[left] + tree[right];
}

cin >> n;
for(int i=1;i<=n;i++)
    cin >> a[i];

sum(1, 1, n);

Full Code Here