1. ## Recursion - Sum

I need to Sum up an array using Recursion however, I need to do 2 recursions. Sum off the first half then the second half then add them together and them add the middle to get the sum.

does this seem okay?

Code:
```int sum (int a[]. int n)
if (n==0)
return 0;

int sumFirstHalf = sum2(a, (n/2) -1)

int sumSecondHalf = sum3(a, (n/2 +1)

return a[n-1] + sumFirstHalf + sumeSecondHalf;```

2. Well the first thing I would do is post code you actually tried to compile since that little snippet is very full of illegal syntax.

The second is: Why sum the halves?

Third: Its only recursion if the function calls itself

The easier method would be to add them up one by one

Code:
```int sum (int a[], int n) // a is the array of numbers, n is the amount of numbers in the array
{
if ( (n-1) == 0 )
return a[0]; // No more need to do recursion
return a[n-1] + sum( /* you figure out what goes here */ );
}```

3. What do you mean? The code you're showing isn't C++ code, and it isn't recursive.

4. This code segment sums up using recursive
Code:
```int sum(int a[], int n)
{
if (n==0)
return 0;

int sumSoFar = sum(a, n-1)
return a[n-1] + sumSoFar```

However the teacher wanted us to split it up in half, so we can do 2 recursions and add those sums up and the middle to get the total. I dont need to write a program just a code fragment, which is was trying to do.

Code:
```int sum (int a[], int n)
{
if (n==0)
return 0;

int sumFirstHalf = sum(a, (n/2) -1)

int sumSecondHalf = sum(a, (n/2) +1)

return a[n-1] + sumFirstHalf + sumeSecondHalf;
}```

5. The easist way is probably to pass a beginning and end value then

using [ ] to denote a set
Basically take 5 numbers:
[1 2 3 4 5]

The first function call would break it down into
[1 2 3] [4 5]

Then it'd do the sum on [1 2 3] breaking it into
[1 2] [3]

Then it'd do it again for [1 2] breaking it into
[1] [2]
then each would return it's value

repeat

Code:
```int sum (int a[], int b, int e)
{
if ( /* End conditions you get to write */ )
return a[ /* what goes here? */ ];
int n = (e-b)+1; // number of numbers in this set
int half = n / 2;
return sum(a, b, b+half) + sum(a, b+half+1, e);  // Sums the first half and the last half
}```

6. Code:
```int sum (int a[], int b, int e)
{
if ( b == e) // assuming no # repeat
return a[0];
int n = (e-b)+1; // couldn't you just put "int n = b" ?
int half = n / 2;
return sum(a, b, b+half) + sum(a, b+half+1, e);  // Sums the first half and the last half
}```
[/QUOTE]

7. don't take my word for it, try it for yourself. I've been known to make mistakes

8. ^^ Well you know more then me, thanks for the help =]

9. Well if you are comfortable with pointer manipulation there is a way to do it with your orignial function header

10. ^^ Not really, I'll try to figure out with the code you tried to help me, its giving me a seg fault @ return sum(a, b, b+half) + sum(a, b+half+1, e);

11. try putting this in at the beginning of the function
Code:
```cout<<"In function sum(), b = "<< b << ", e = " << e << ".  Values are: ";
for (int i = b; i < e; i++)
cout<<' ' <<a[i];
cout<<endl;```
That should help you find out if you are getting any erronous data.

Oh and by the way: return a[0]; is wrong

Edit: After some testing I have found at least two logic errors in my code. While the structure is still correct I was adding 1 to numbers I shouldn't have.

I will tell you however that e isn't the index of the last number, its one past it. So the call would look something like:
Code:
```  int arr[] = { 1, 2, 3, 4, 5 };
int s = sum(arr, 0, 5);```
you can do it where e is the last index but its actually more messy IMO.