Thread: 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;

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

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

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
}

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

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

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

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

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.