Алгоритм «разделяй и властвуй» для суммы массива целых чисел

В вашем коде:

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

мы можем проиллюстрировать ошибку на примере, где массив равен { 2, 3, 4, 5, 6, 9} и size = 6.

теперь, когда вы делаете mid = size / 2, а затем:

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

число 5 добавляется дважды (один раз в lsum, а затем в rsum), потому что mid == (size - mid).

Кроме того, вызов sumArray() в rsum должен иметь параметры sumArray(anArray + (mid + 1), --rsize), так как элемент mid уже добавлен в lsum.

С другой стороны, вы можете использовать гораздо более простой код для рекурсии, например...

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

Как сказал Харис, в вашем коде вы добавляете одно и то же число как к правой сумме, так и к левой сумме; однако в вашем коде есть гораздо большая проблема.

Вы всегда передаете один и тот же массив своим рекурсивным вызовам lsum и rsum. Сначала я думал, что это всего лишь часть вашей реализации и что об этом позаботится параметр размера. Однако параметр размера не работает так, как вы, возможно, предполагали. Все, что делает ваш алгоритм, — это уменьшает параметр size до тех пор, пока он не достигнет 1. Затем запускается базовый случай, и в результате всегда возвращается первый элемент исходного массива. Почему? Вы никогда не разбиваете массив в своем коде, поэтому один и тот же массив сохраняется при каждом рекурсивном вызове (даже в базовом случае).

Чтобы решить эту проблему, все, что sumarray() должен сделать, это разделить массив на левую половину и правую половину на основе промежуточного вычисления и рекурсивно передать этот новый массив до тех пор, пока размер массива не станет равным 1 (базовый случай), и вы вернете элемент в массиве. Это эффективно разбивает массив на отдельные элементы, и все, что функция должна сделать на этом этапе, — это сложить lsum и rsum.

Псевдокод:

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
 }