Python List Slicing Efficiency

Question

In the following code:

def listSum(alist): """Get sum of numbers in a list recursively.""" sum = 0 if len(alist) == 1: return alist[0] else: return alist[0] + listSum(alist[1:]) return sum 

Is a new list created every time I do listSum(alist[1:]) ?

If so, is this the recommended way or can I do something more efficient? (Not for a specific function - this is an example), but rather when I want to process a certain part of the list in general.)

Edit:

Sorry, if I embarrassed anyone, I am not interested in the efficient implementation of sum , this served as an example for using slicing in this way.

Answer 1

Yes, he creates a new list every time. If you can avoid using iteration, you can use itertools.islice or juggle iter(list) (if you only need to skip some items at the beginning). But this gets messy when you need to determine if the argument is empty or has only one element - you should use try and catch StopIteration . Edit: You can also add an additional argument specifying where to start. Unlike the @marcadian version, you must make it the default argument so as not to burden the caller with this and avoid errors from the wrong index being passed from the outside.

Often it is better not to get into this situation - either write your code so that you can let for deal with iteration (read: do not use recursion). Alternatively, if the slice is small enough (perhaps because the list is generally small), still bite the bullet and the slice is easier, and when slicing it has linear time, the constant coefficient is really tiny.

Answer 2

I can think of some options:

• use the built-in sum function for this particular case
• If you really need recursion (for some reason), go to the same list by calling the function, as well as by the index of the current element, so you don't need to slice the list (which creates a new list)

option 2 works as follows:

 def f_sum(alist, idx=0): if idx >= len(alist): return 0 return alist[idx] + f_sum(alist, idx + 1) f_sum([1, 2, 3, 4]) a = range(5) f_sum(a) 

Answer 3

This is another way if you have to use tail-recursive. In many other languages, this is more efficient than regular recursions in terms of space complexity. Unfortunately, this is not the case in python because it does not have built-in support for optimizing tail calls. It is good practice to take into account if you are studying recursion nonetheless.

 def helper(l, s, i): if len(l) == 0: return 0 elif i < len(l) - 1: return helper(l, s + l[i], i + 1) else: return s + l[i] def listSum(l): return helper(l, 0, 0)