Help with recursion sum

[waranthem]

The sum of {1,2,3,4,5,6,7,8,9} should be 45. Sum is displaying 45. Binary Sum is only displaying 36.

 int BinarySUM (int Array [], int i, int n)
    {
        if (n == 1){
            return Array [i];
        }
        else{
            return BinarySUM (Array, i, (n/2)) + BinarySUM (Array, i + (n/2), (n/2));
        }
    }

    int main ()
    {
        const int n = 9;
        int Array [n]  = {1,2,3,4,5,6,7,8,9};
        int Sum = 0;

        for (int i = 0; i < n; i++){
            cout << Array [i] << " ";
        }

        for (int i = 0; i < n; i++){
            Sum += Array [i];
        }

        cout << "\n" << Sum;
        cout << "\n" << BinarySUM (Array, 0, n);
    }

[lastchance]

return BinarySUM (Array, i, n/2) + BinarySUM (Array, i + n/2, n-n/2);

Could you possibly include your headers.

[waranthem]

#include <stdlib.h>
#include <iostream>

What exactly does n-n/2 do?

[lastchance]

waranthem wrote:

What exactly does n-n/2 do?

Basically, n/2 will suffer from integer division. You are compensating for that. Looked at another way, you can't divide an odd number into two equal parts.

For example, 9/2 will integer-divide to 4. If you put n/2 in each part you would get 4 elements in each part sum and exclude the 9th element (which was the amount by which your sum was wrong).

If, on the other hand, you split it as n/2 and n-n/2 then you would get 4 elements in the first part sum and 9-4=5 in the second, so you won't lose any elements in the sum.

If you put n/2 in both parts, then your sum would only work where you never suffered from losses due to integer division; i.e. when n is a power of 2 (for example, 8). However, here you have n=9 and it would lose an element on the first split.