Recursion - Sum

This is a discussion on Recursion - Sum within the C++ Programming forums, part of the General Programming Boards category; I need to Sum up an array using Recursion however, I need to do 2 recursions. Sum off the first ...

  1. #1
    Registered User
    Join Date
    Apr 2003
    Posts
    82

    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. #2
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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. #3
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    What do you mean? The code you're showing isn't C++ code, and it isn't recursive.

  4. #4
    Registered User
    Join Date
    Apr 2003
    Posts
    82
    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;
        }
    Last edited by gqchynaboy; 09-13-2005 at 11:39 PM.

  5. #5
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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. #6
    Registered User
    Join Date
    Apr 2003
    Posts
    82

    Smile

    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]
    Last edited by gqchynaboy; 09-14-2005 at 12:20 AM.

  7. #7
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    don't take my word for it, try it for yourself. I've been known to make mistakes

  8. #8
    Registered User
    Join Date
    Apr 2003
    Posts
    82
    ^^ Well you know more then me, thanks for the help =]

  9. #9
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Well if you are comfortable with pointer manipulation there is a way to do it with your orignial function header

  10. #10
    Registered User
    Join Date
    Apr 2003
    Posts
    82
    ^^ 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. #11
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Application Repeatition
    By lgcarter in forum C Programming
    Replies: 3
    Last Post: 06-16-2009, 03:07 PM
  2. Replies: 1
    Last Post: 05-28-2009, 02:28 PM
  3. Minor Problem
    By stewie1986 in forum C Programming
    Replies: 6
    Last Post: 11-30-2007, 08:40 AM
  4. a sum equal to or in excess of 100
    By lyoncourt in forum C Programming
    Replies: 6
    Last Post: 10-07-2007, 06:43 PM
  5. string to int conversion not using atoi()
    By linucksrox in forum C Programming
    Replies: 2
    Last Post: 05-19-2004, 01:17 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21