Thread: Recursion help

  1. #1
    Registered User
    Join Date
    Oct 2005
    Posts
    21

    Recursion help

    I need to write a program that recursively calculates the sum of UP TO 20 array elements provided by the user. Currently the program is resulting in an error when I attempt to run it. I'm also not sure if my recursive function does what I need it to in it's current state.

    Code:
     #include <stdio.h>
      #include <string.h>
    
      int sum(int i, int element[i]); /*Prototype for recursive addition */
      
      int main(void)
     {
      int max_elements, element[(max_elements-1)], i, result;
      i=0;
      printf("Determine the number of elements to be entered from 1 to 20: ");
      scanf("%d", &max_elements);
      
        for(i=0; i<max_elements; i++)
         { printf("Enter an integer: ");
           scanf("%d", element[i]);
           printf("\n");
         }
      result=sum(i, &element[i]);
      printf("The sum of the elements is %d", result);
      return 0;
     }
    
      int sum(int i, int element[i])
    
    
     { int max_elements;
        if (i==max_elements)
          return 0;
        else
          return (sum(i+1, element[i+1]+&element[i]));
     }
    Where am I going wrong?

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    > int max_elements, element[(max_elements-1)]
    1. C doesn't have variable length arrays
    2. You haven't even initialised max_elements, so assuming it even compiles by some compiler extension, the size could be anything
    Since you state "max 20", just go with int element[20];

    > scanf("%d", element[i]);
    You forgot the &
    scanf("%d", &element[i]);

    Think about the recursive function in these terms
    - if there is only one element in the array, the sum is that element
    - else the sum is the last element, plus the result of the recursive call to sum n-1 elements

    Code:
    int sum ( int n, int *arr ) {
      if ( n == 0 ) {
        return arr[n];
      } else {
        return arr[n] + sum(n-1,arr);
      }
    }

  3. #3
    Registered User
    Join Date
    Oct 2005
    Posts
    21

    Some updates...

    Code:
     #include <stdio.h>
      #include <string.h>
    
      int sum(int i, int element[i]); /*Prototype for recursive addition */
      
      int main(void)
     {
      int max_elements, element[20], i, result;
      i=0;
      printf("Determine the number of elements to be entered from 1 to 20: ");
      scanf("%d", &max_elements);
      
        for(i=0; i<max_elements; i++)
         { printf("Enter an integer: ");
           scanf("%d", &element[i]);
         }
      result=sum(i, &element[i]);
      printf("The sum of the elements is %d", result);
      return 0;
     }
    
      int sum(int i, int element[i])
      
     {  
        if (i==0)
         {
          return element[i];
         }
        else
         { 
          return element[i]+ sum(i-1, &element[i-1]);
         }
     }
    The code now runs, but the sum is being displayed as '32' regardless. I realize that you suggested trying the else statement of:
    return arr[i]+sum(i-1, arr);
    That resulted in a huge negative sum value.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    Code:
    #include <stdio.h>
    int sum ( int n, int *arr ) {
      if ( n == 0 ) {
        return arr[n];
      } else {
        return arr[n] + sum(n-1,arr);
      }
    }
    int main ( ) {
      int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
      printf("%d\n", sum(9,arr) );
    }
    Or here perhaps http://cboard.cprogramming.com/showthread.php?t=73404

  5. #5
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    There is nothing wrong with Salems example.
    It's the way you call the function.
    Code:
      result=sum(i, &element[i]);
    What is the value of i here ?.
    Where points &element[i] ? is that the array ?
    Another thing is that not many ( if any ) compilers accept
    Code:
      int sum(int i, int element[i]); /*Prototype for recursive addition */
    Kurt
    EDIT: I'm a little slow.

  6. #6
    Registered User
    Join Date
    Oct 2005
    Posts
    21
    If the sum is calculated to be greater than 20, the program has no problem displaying it. If the sum is less than 20, however, the program feels the need to add 20 to it? I implemented an if/ else statement to try and correct it, but it was unsuccessful.
    Code:
    #include <stdio.h>
      #include <string.h>
    
      int sum(int i, int element[i]); /*Prototype for recursive addition */
      
      int main(void)
     {
      int max_elements, element[20], i, result, total;
      i=0;
      printf("Determine the number of elements to be entered from 1 to 20: ");
      scanf("%d", &max_elements);
      
        for(i=0; i<max_elements; i++)
         { printf("Enter an integer: ");
           scanf("%d", &element[i]);
         }
      result=sum(max_elements, &element[i]);
       if (sum(max_elements, element)<20)
       {
        total=((sum(max_elements, element))-20);
        printf("The sum is %d", total);
       }
       else
       {
        printf("The sum is %d", sum(max_elements,element));
       }
      return 0;
     }
    
      int sum(int i, int element[i])
    
    
     {  
        if (i==0)
         {
          return element[i];
         }
        else
         { 
          return element[i]+ sum(i-1, element);
         }
     }

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    result=sum(max_elements, &element[i]);
    This should just be:
    Code:
    result = sum( max_elements, element );
    What exactly are you trying to do here?
    Code:
     if (sum(max_elements, element)<20)
    Quzah.
    Hope is the first step on the road to disappointment.

  8. #8
    Registered User
    Join Date
    Oct 2005
    Posts
    21
    Quote Originally Posted by quzah
    What exactly are you trying to do here?
    Code:
     if (sum(max_elements, element)<20)
    Quzah.
    That was an attempt to fix the sum problem I am getting. A calculated sum that was less than 20 was having 20 added to it. A sum greater than 20 was outputted normally. So I tried to write a line that would fix any sum smaller than 20.

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    But it is supposed to retun the sum of the entered values, so why on earth ... anyway, it's better to try and find out what's wrong, rather than try to cobble scraps together to get the desired output.


    Quzah.
    Hope is the first step on the road to disappointment.

  10. #10
    Registered User
    Join Date
    Oct 2005
    Posts
    21
    Quote Originally Posted by quzah
    But it is supposed to retun the sum of the entered values, so why on earth ... anyway, it's better to try and find out what's wrong, rather than try to cobble scraps together to get the desired output.


    Quzah.
    I realize that, but for whatever reason that isn't working, and neither is this attempt to patch it up.

  11. #11
    Logic Junkie
    Join Date
    Nov 2005
    Posts
    31
    I don't know what you are talking about, your code from above works fine for me. Kill the if-else, and it is working, displayin correct results for values under 20 too.
    -S

  12. #12
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    element[max_elements] is past the end of the array.
    You have to call sum this way
    Code:
    total=sum(max_elements-1, element);
    Kurt

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 09:37 AM
  3. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  4. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 09:24 AM
  5. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 02:29 PM