Search code examples
c++arraysalgorithmrecursiondivide-and-conquer

Divide and conquer algorithm for sum of integer array


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.


Solution

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