Add elements through array recursively

This is a discussion on Add elements through array recursively within the C++ Programming forums, part of the General Programming Boards category; Hello all, I am having tremendous problems writing this program. I know that I should be able to write this ...

  1. #1
    Registered User
    Join Date
    Sep 2003
    Posts
    48

    Unhappy Add elements through array recursively

    Hello all, I am having tremendous problems writing this program. I know that I should be able to write this proram in 15 lines (maybe even less) but I am having trouble finding the correct method to write it. I've been trying to write it for a few days now and am frustrated because I know that it is a simple mistake that I am making.
    I am trying to write a program that sums the elements of an array.
    It's supposed to take 3 arguments that I believe I entered correctly
    m: start position of array (1<=m<=10
    n:end position of array (1<=n<=10 and m<=n)
    int_array[]:integer array

    Basically I am trying to get the program to add the elements (m through n) using recursion.
    Another part of this is that I have to use the pointer but I'll figure that one out later

    Just please let me know if I am way off because I havent had too many problems with C++ up until now. Should I start from scratch?? Is my sum function all wrong??

    In advance, Thank you for any help you can provide

    Code:
    #include <iostream.h>
    
    int sum(int); // function prototype
    
    int main()
    {
    	int int_array[10]={1,2,3,4,5,6,7,8,9,10};
      int m,n;
    	
    	cout << "Please enter the starting position: ";
       cin >> m;
    	cout<< "Please enter the end position:  ";
    	cin>>n;
    return 0;
    
     // end main
    
    
    }
    
    int sum ()
    
    {  
       if ( 1 <= m<=10 && 1<=n<10 && m<=n)  
          return int_array[m]+int_array[n];
    
      
    
       // recursive step
       else             
          return 1;
    
    } // end function

  2. #2
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    Personally, I'd use a loop to do this rather than a recursive function, but you can probably use recursion if you wish.

    In general, recusive functions need to have a starting and ending state and something to do in between. One of the steps in between is to call the function again using a new value generated within the called function.

    I would validate m and n outside of sum(). I would pass sum() the values of m and n and the array itself. Inside sum() I would have a variable called temp. If m == n I would return the value of array[m]. Otherwise I would assign temp the sum of the value of array[m] and the return value of sum() called using the next value of m, which I would generate by the post increment operator. In this way the sum would be calculated backwards, starting with the value of array[n] and adding the value of array[n -1] with each unwinding of the recursive calls.
    Code:
    int sum(int, int, int*);
    
    int main()
    {
    //declare int_array and obtain and verify m and n
    //then
    int answer = sum(m, n, int_array);
    //do something with answer
    }
    
    int sum(int m, int n, int * int_array)
    {
       int temp = 0;
       if(m == n)  
          return int_array[m];
       else
          temp = int_array[m++] + sum(m, n, int_array);
          return temp;
    }
    If m were 0 and n were 2 with int_array as in your post, then there will be three calls to sum(). at the third call to sum() m will equal n, so the value of int_array[2] will be returned to the second call to sum() and added to int_array[1] making temp = 2 + 3; then temp will be returned to the first call of sum() making temp = 1 + 5. Then temp will be returned to main() where it will be assigned to answer.

  3. #3
    Registered User
    Join Date
    Sep 2003
    Posts
    48

    Thanks

    Thank you very much "elad". Thanks to your notes, I was able to see where I went wrong and rewrite the code so that it would fit the program I was trying to write. I am still missing a line or two but am definitely on the right track now.

    Thanks

  4. #4
    Registered User
    Join Date
    Sep 2003
    Posts
    135
    Originally posted by elad
    Code:
    int sum(int m, int n, int * int_array)
    {
       int temp = 0;
       if(m == n)  
          return int_array[m];
       else
          temp = int_array[m++] + sum(m, n, int_array);
          return temp;
    }
    We can simplify this by removing temp:
    Code:
    int sum(int m, int n, int * int_array)
    {
       if(m == n)  
          return int_array[m];
       else
          return int_array[m++] + sum(m, n, int_array);
    }
    Also possible, though less readable, is:
    Code:
    int sum(int m, int n, int * int_array)
    {
       return m==n?int_array[m]:int_array[m++] + sum(m,n,int_array);
    }

  5. #5
    Registered User
    Join Date
    Jan 2003
    Posts
    311
    You are missing a sequence point.

    int temp = int_array[m++];
    return temp + sum(m,n,int_array);

    Though the whole thing reeks of homework.

    return m==n?int_array[m]:sum(m,(n+m)/2,int_array) + sum((n+m)/2+1,n,int_array);

  6. #6
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    Originally posted by grib
    Though the whole thing reeks of homework.
    I agree that it sounds like this is a homework assignment (why else use recursion?), but this isn't nearly as bad as other posts regarding homework assignments. At least silicon didn't post the assignment verbatim or write a post that didn't have code. He tried his best on his own. He wrote his own code and posted it. Then, we pointed him in the right direction. I think that's how this forum is supposed to work.
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  7. #7
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    >I think that's how this forum is supposed to work.

    I was thinking the same thing.

  8. #8
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Location
    Mt. Prospect, IL
    Posts
    2,572
    I agree with the both of you!

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. using realloc for a dynamically growing array
    By broli86 in forum C Programming
    Replies: 10
    Last Post: 06-27-2008, 05:37 AM
  2. Resource Management question..
    By Raigne in forum C++ Programming
    Replies: 37
    Last Post: 03-08-2008, 08:36 AM
  3. Problem with assigning value to array elements
    By sagitt13 in forum C++ Programming
    Replies: 3
    Last Post: 08-17-2004, 11:26 AM
  4. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM
  5. A simple question about selecting elements in an array
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 08-30-2001, 10:37 PM

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