Thread: Sum of a list

    #1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2009
    Location
    Kansas
    Posts
    36
    Rep Power
    5

    Sum of a list


    Alright all help is greatly appreciated. I have to make a program in an interative fashion that finds the sum of a list, but only using a single "def" function, and then include some test invocations that prove that the progam works, I figured out how to do that just fine. However we are asked to do it in recurrsive fashion, i have never heard of this and would like some help.

    here is my code for my interative version:

    Code:
    #Defined the function that finds the sum of List x
    def sum_of_list(x):
        return sum(x)
    
    
    #tests that show the functions works
    x=(1,2,3,4)
    print "the sum of list" + str(x) + "is " + str (sum_of_list(x))
    
    x=(1,3,5,7)
    print "the sum of list" + str(x) + "is " + str (sum_of_list(x))
    
    x=(2,4,6,8)
    print "the sum of list" + str(x) + "is " + str (sum_of_list(x))
  2. #2
  3. Transforming Moderator
    Devshed Supreme Being (6500+ posts)

    Join Date
    Mar 2007
    Location
    Washington, USA
    Posts
    14,143
    Rep Power
    9398
    Originally Posted by iowabowhunter1
    here is my code for my interative version:
    That's not iterative. All you did was use another function to do the work. I'm pretty sure you're supposed to come up with your own code that does the summation.

    The recursive solution is to return the first number in the list (if there's only one) or return the first + the result from the recursive call using the rest of the list. Kinda looks like
    Code:
    sum of [1, 2, 3] = 1 + (sum of [2, 3] = 2 + (sum of [3] = 3))
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    London, England
    Posts
    1,585
    Rep Power
    1373
    I presume this is a homework assignment.

    <rant>
    It really bugs me that teachers set sh*t like this. There are are good uses for recursion, but this is not one of them. In fact using recursion for this problem is a terrible idea, since
    1) there is a perfectly good builtin function to do this, which the OP used.

    2) using a recursive function for this is going to be way slower than using an iterative loop, and much, much slower than using 'sum', which is implemented in C.

    3) there is a limit on how deep your recursion can go. Using a recursive function to sum a list will fail for long lists.

    If the teacher wants to teach recursion then they should use problems where it is appropriate, such as for tree structures like directory listings.

    </rant>

    Dave
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2008
    Posts
    96
    Rep Power
    45
    python Code:
    def rGetSum(L):
        if len(L) == 1:
            return L[0]
        else:
            L[1] += L[0]
            return  rGetSum(L[1:])


    the list is slice after each call, saves the current sum on the 2nd index and remove the 1st index.

    There's a trivial issue before where recursive calls returns None... I've read it in some mailing list and the solution was solve by using type() function.
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2008
    Location
    Germany
    Posts
    25
    Rep Power
    0
    This sort of questions arises very often here.
    python Code:
     
    def recsum(ls):
      if not ls:
        return 0
      return ls[0] + recsum(ls[1:])
     
    # test
    assert recsum([]) == 0
    assert recsum([1]) == 1
    assert recsum(range(10)) == sum(range(10))
     
     
    def tailrecsum(ls, accu=0):
      if not ls:
        return accu
      return tailrecsum(ls[1:], ls[0] + accu)
     
    # test
    assert tailrecsum([]) == 0
    assert tailrecsum([1]) == 1
    assert tailrecsum(range(10)) == sum(range(10))


    Yes, it is an awkward, non-real-world example, but it seems to me that
    a lot of people have difficulties to understand these concepts.


    yipyip
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2009
    Location
    Kansas
    Posts
    36
    Rep Power
    5
    Originally Posted by DevCoach
    I presume this is a homework assignment.

    <rant>
    It really bugs me that teachers set sh*t like this. There are are good uses for recursion, but this is not one of them. In fact using recursion for this problem is a terrible idea, since
    1) there is a perfectly good builtin function to do this, which the OP used.

    2) using a recursive function for this is going to be way slower than using an iterative loop, and much, much slower than using 'sum', which is implemented in C.

    3) there is a limit on how deep your recursion can go. Using a recursive function to sum a list will fail for long lists.

    If the teacher wants to teach recursion then they should use problems where it is appropriate, such as for tree structures like directory listings.

    </rant>

    Dave
    Yeah this is an intro class and I do not understand anything he teaches, he just jumps around and doesnt teach us the right method, I dont know any like commands just while loops, if and elif statements and thatts about it. I wish i could drop this class, a friend of mine is in an actual computer sci I class and he is doing easier stuff than i am. pure crap if you ask me.
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2009
    Location
    Kansas
    Posts
    36
    Rep Power
    5
    Originally Posted by yipyip
    This sort of questions arises very often here.
    python Code:
     
    def recsum(ls):
      if not ls:
        return 0
      return ls[0] + recsum(ls[1:])
     
    # test
    assert recsum([]) == 0
    assert recsum([1]) == 1
    assert recsum(range(10)) == sum(range(10))
     
     
    def tailrecsum(ls, accu=0):
      if not ls:
        return accu
      return tailrecsum(ls[1:], ls[0] + accu)
     
    # test
    assert tailrecsum([]) == 0
    assert tailrecsum([1]) == 1
    assert tailrecsum(range(10)) == sum(range(10))


    Yes, it is an awkward, non-real-world example, but it seems to me that
    a lot of people have difficulties to understand these concepts.


    yipyip
    alright so the first one is interavitve fashion and the second one is in recursive fashion? Thank you very much for everyones help!!! I would be totally lost, I email my teacher and he just sends back computer jargon and doesnt answer my questions just goes around them, i went to his office hours once and he couldnt really tell me anything about python because he doesnt work with it that much at all i guess, so why assign assignments in it!!?!?!?!?!?!
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2008
    Location
    Germany
    Posts
    25
    Rep Power
    0
    No, both functions are recursive.

    A very rough description:

    - tailrecsum()
    This function is called tail-recursive.
    Generally speaking this means, that the accumulated result can be given back directly, after walking
    down the called functions.

    - recsum()
    The result is achieved by walking down and walking up the called functions.


    yipyip
  16. #9
  17. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2009
    Location
    Kansas
    Posts
    36
    Rep Power
    5
    Originally Posted by yipyip
    No, both functions are recursive.

    A very rough description:

    - tailrecsum()
    This function is called tail-recursive.
    Generally speaking this means, that the accumulated result can be given back directly, after walking
    down the called functions.

    - recsum()
    The result is achieved by walking down and walking up the called functions.


    yipyip
    how do i go bout making a interavtive fashioned one?
  18. #10
  19. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2008
    Location
    Germany
    Posts
    25
    Rep Power
    0
    What do you mean by "interarvtive"?
    You surely mean "iterative".

    If you did not come up with a solution like
    python Code:
     
    def itersum(ls):
      result = 0
      for x in ls:
        result += x
      return result

    by now, you are at the very, very beginning.
    Try to learn Python with "A byte of Python" (for example),
    this is the best advice i can give you at the moment.


    yipyip
  20. #11
  21. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2009
    Posts
    5
    Rep Power
    0
    I presume this is a homework assignment.

IMN logo majestic logo threadwatch logo seochat tools logo