### Help with recursion sum

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.

 ``12345678910111213141516171819202122232425262728`` `````` 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); } ``````
Last edited on
` return BinarySUM (Array, i, n/2) + BinarySUM (Array, i + n/2, n-n/2);`

Last edited on
#include <stdlib.h>
#include <iostream>

What exactly does n-n/2 do?
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.
Last edited on
Topic archived. No new replies allowed.