0

I am learning the recursive functions. I completed an exercise, but in a different way than proposed.

"Write a recursive function which takes a list argument and returns the sum of its integers."

L = [0, 1, 2, 3, 4]  # The sum of elements will be 10

My solution is:

def list_sum(aList):
    count = len(aList)
    if count == 0:
    return 0

    count -= 1
    return aList[0] + list_sum(aList[1:])

The proposed solution is:

def proposed_sum(aList):
    if not aList:
        return 0
    return aList[0] + proposed_sum(aList[1:])

My solution is very clear in how it works.

The proposed solution is shorter, but it is not clear for me why does the function work. How does if not aList even happen? I mean, how would the rest of the code fulfill a not aList, if not aList means it checks for True/False, but how is it True/False here?

I understand that return 0 causes the recursion to stop.

As a side note, executing without if not aList throws IndexError: list index out of range.

Also, timeit-1million says my function is slower. It takes 3.32 seconds while the proposed takes 2.26. Which means I gotta understand the proposed solution.

Aleksik
  • 47
  • 1
  • 9
  • 1
    Possible duplicate of [Best way to check if a list is empty](http://stackoverflow.com/questions/53513/best-way-to-check-if-a-list-is-empty) – FujiApple Aug 25 '16 at 11:45
  • In python, a empty list can be used in the if clause with value False – tianwei Aug 25 '16 at 11:45
  • `if len(aList) == 0` and `if not aList` return the same thing: `True` if the list is empty and `False` otherwise. – DeepSpace Aug 25 '16 at 11:48
  • I see. So `if not aList` checks if the list is empty, if so, it returns 0. Okay. But in this case, how does the list become empty? Just because the code asked for it's every element? – Aleksik Aug 25 '16 at 11:49
  • @Aleksik This recursion abuses the fact that list slicing doesn't raise `IndexError`. It keeps separating the given list to its first element and the rest of it. At some point down the line the function will get a list with a single element, and it will try to separate the list to its first (and only) element and the rest of it (which will get you an empty list). You can replicate this behavior: `li = [2] ; print(li[0], li[1:]) >> 2, []` – DeepSpace Aug 25 '16 at 12:12

5 Answers5

1
not aList

return True if there is no elements in aList. That if statement in the solution covers edge case and checks if input parameter is not empty list.

drootnar
  • 133
  • 1
  • 2
  • 10
1

On the call of the function, aList will have no elements. Or in other words, the only element it has is null. A list is like a string or array. When you create a variable you reserve some space in the memory for it. Lists and such have a null on the very last position which marks the end so nothing can be stored after that point. You keep cutting the first element in the list, so the only thing left is the null. When you reach it you know you're done.

If you don't use that condition the function will try to take a number that doesn't exist, so it throws that error.

Dark
  • 89
  • 4
  • "On the call of the function, aList will have no elements. " Why won't it have any elements? Is it because `aList[0] + proposed_sum(aList[1:])` covers for the whole list? – Aleksik Aug 25 '16 at 11:52
  • 1
    @Aleksik because if you do ex: `aList = [4]` then `aList[1:]` you quit that 4, so you get `[]` – Raskayu Aug 25 '16 at 11:59
  • 1
    @Aleksik because on every step, because of how you call it (`aList[0] + proposed_sum(aList[1:])` ) you drop the first number. At one point, you will cut the last number and run the function again. There that if condition breaks the cycle, because it will see just an empty address. – Dark Aug 25 '16 at 12:17
  • Oh wow. So it means that when I use the arguments `[1, 2, 3]` and then `return aList[0]`, in the function I am left with arguments `[2, 3]`? My mind is blown. And then each time I call `aList[0]` up to the point where I am left with nothing in the arguments, which is `aList = []`, which enables `if not aList:` because the list is empty == not True. Amazing! I didn't realize that elements get dropped/quit/cut. This opens up so many possibilities. – Aleksik Aug 25 '16 at 12:30
  • 1
    @Aleksik Not exactly, the `proposed_sum(aList[1:])` runs the function again but for [2, 3]. You need `aList[0] + proposed_sum(aList[1:])` to get the sum between the first element in the list and the sum of the other number. But the sum of the other numbers is the sum between the first element of the remaining numbers and the rest of them and so on. It's like: the result=1+sum([2,3])=1+2+sum([3])=1+2+3+sum(nothing). When you type `aList[1:]` it is equal to `[2,3]`, because it skips the first number. – Dark Aug 25 '16 at 12:35
  • Yes I understand that I need the whole `return aList[0] + proposed_sum(aList[1:])` for the list to get smaller and smaller up to the []. What you told me here is the best. – Aleksik Aug 25 '16 at 12:37
  • @Aleksik Glad you got it. Recursives might look a bit entangled at the beginning but with practice you start seeing what they really do. – Dark Aug 25 '16 at 12:43
1

Python considers as False multiple values:

  • False (of course)
  • 0
  • None
  • empty collections (dictionaries, lists, tuples)
  • empty strings ('', "", '''''', """""", r'', u"", etc...)
  • any other object whose __nonzero__ method returns False

in your case, the list is evaluated as a boolean. If it is empty, it is considered as False, else it is considered as True. This is just a shorter way to write if len(aList) == 0:

in addition, concerning your new question in the comments, consider the last line of your function:

return aList[0] + proposed_sum(aList[1:])

This line call a new "instance" of the function but with a subset of the original list (the original list minus the first element). At each recursion, the list passed in argument looses an element and after a certain amount of recursions, the passed list is empty.

Tryph
  • 5,946
  • 28
  • 49
1

You are counting the items in the list, and the proposed one check if it's empty with if not aList this is equals to len(aList) == 0, so both of you use the same logic.

But, you're doing count -= 1, this has no sense since when you use recursion, you pass the list quiting one element, so here you lose some time.

According to PEP 8, this is the proper way:

• For sequences, (strings, lists, tuples), use the fact that empty sequences are false.

Yes: if not seq:
     if seq:

No: if len(seq)
    if not len(seq)

Here is my amateur thougts about why:

This implicit check will be faster than calling len, since len is a function to get the length of a collection, it works by calling an object's __len__ method. This will find up there is no item to check __len__.

So both will find up there is no item there, but one does it directly.

Raskayu
  • 735
  • 7
  • 20
1

For understand this function, let's run it step by step : step 0 :

L=[0,1,2,3,4]
proposed_sum([0,1,2,3,4])
L != []
return  l[0] + proposed_sum([1,2,3,4])

step 1 calcul proposed_sum([1,2,3,4]):

proposed_sum([1,2,3,4])
L != []
return  l[0] + sum([2,3,4])

step 2 calcul proposed_sum([2,3,4]):

proposed_sum([2,3,4])
L != []
return  l[0] + sum([3,4])

step 3 calcul proposed_sum([3,4]):

proposed_sum([3,4])
L != []
return  l[0] + sum([4])

step 4 calcul proposed_sum([4]):

proposed_sum([4])
L != []
return  l[0] + sum([])

step 5 calcul proposed_sum([]):

proposed_sum([])
L == []
return  0

step 6 replace:

proposed_sum([0,1,2,3,4])

By 

proposed_sum([]) + proposed_sum([4]) + proposed_sum([3,4]) + proposed_sum([2,3,4]) + proposed_sum([1,2,3,4])+ proposed_sum([0,1,2,3,4])

= 

(0)  +  4 + 3 + 2 + 1 + 0
khelili miliana
  • 3,730
  • 2
  • 15
  • 28