Divide et impera sum of the elements of an array bug

Question

I wrote the following function to calculate the sum of all the elements in a vector using the divide et impera method

int Sum(std::vector<int> v, int left, int right)
{
int mid = (left + right) / 2;

if (left >= right)
    return v[mid];
else
    return Sum(v, left, mid - 1) + Sum(v, mid + 1, right);
}

//in main:
vector <int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

cout << Sum(v, 0, v.size() - 1);

However in the given example it outputs 37 instead of 55. I went through it with a debugger and it seems to skip certain numbers. I tried changing left >= right to left > right and it still gives me a wrong answer (56) although I think it should be left => right logically speaking.

What is wrong in the code?

Answer 1

Main problem: The recursion excludes mid from both sub-sums.

Secondary problem: It may happen that left>right (though with reasonable initial input, at worst left == right + 1). In this case you want to return 0.

So perhaps

if ( left > right ) 
   return 0;
else
   return Sum(v, left, mid-1) + v[mid] + Sum(v, mid+1, right);