October 22nd, 2009, 12:08 AM

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))
October 22nd, 2009, 01:18 AM

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))
October 22nd, 2009, 03:21 AM

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
October 22nd, 2009, 04:53 AM

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.
October 22nd, 2009, 07:11 AM

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, nonrealworld example, but it seems to me that
a lot of people have difficulties to understand these concepts.
yipyip
October 23rd, 2009, 10:43 AM

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.
October 23rd, 2009, 10:45 AM

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, nonrealworld 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!!?!?!?!?!?!
October 23rd, 2009, 11:36 AM

No, both functions are recursive.
A very rough description:
 tailrecsum()
This function is called tailrecursive.
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
October 25th, 2009, 05:18 PM

Originally Posted by yipyip
No, both functions are recursive.
A very rough description:
 tailrecsum()
This function is called tailrecursive.
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?
October 26th, 2009, 06:42 AM

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
October 26th, 2009, 07:47 AM

I presume this is a homework assignment.