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.
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;
}