16

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 when I do listSum(alist[1:])?

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

Edit:

Sorry if I confused anyone, I am not interested in an efficient sum implementation, this served as an example to use slicing this way.

i_am_finally_learning_python
  • 187
  • 1
  • 1
  • 7

3 Answers3

11

Yes, it creates a new list every time. If you can get away with using an iterable, you can use itertools.islice, or juggle iter(list) (if you only need to skip some items at the start). But this gets messy when you need to determine if the argument is empty or only has one element - you have to use try and catch StopIteration. Edit: You could also add an extra argument that determines where to start. Unlike @marcadian's version, you should make it a default argument to not burden the caller with that and avoid bugs from the wrong index being passed in from the outside.

It's often better to not get in that sort of situation - either write your code such that you can let for deal with iteration (read: don't use recursion like that). Alternatively, if the slice is reasonably small (possibly because the list as a whole is small), bite the bullet and slice anyway - it's easier, and while slicing is linear time, the constant factor is really tiny.

  • 2
    So, assuming as a toy example that I have a fairly large list of numbers, and I want to add 2 to half of them. Is something like `for number in mylist[middle:]: number+=2` acceptable? (Or it is not considered a good practice to slice a really large list?) – i_am_finally_learning_python Aug 26 '13 at 01:22
  • 2
    @i_am_finally_learning_python Leaving aside that example doesn't work - doesn't alter the contents of `mylist` (and the easiest way to make it do that involves not slicing anything) - it depends. Slicing does have the big plus that it's usually simpler and prettier than the alternative. But depending on what "fairly large" is, how often that code executes, and other factors, it may be annoyingly slow and the less readable slice-less alternative is worth it. It's hard to say in general. –  Aug 26 '13 at 01:25
  • Oh but of course, I guess I got overexcited with those python for loops!! That cleared some stuff up, thanks. – i_am_finally_learning_python Aug 26 '13 at 01:31
4

I can think of some options:

  1. use builtin function sum for this particular case
  2. If you really need recursion (for some reason), pass in the same list to the function call and also index of current element, so you don't need to slice the list (which creates new list)

option 2 works like this:

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)
marcadian
  • 2,608
  • 13
  • 20
-1

This is another way if you must use recursion (tail-recursive). In many other languages this is more efficient than regular recursions in terms of space complexity. Unfortunately this isn't the case in python because it does not have a built-in support for optimizing tail calls. It's a good practice to take note of if you are learning 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)
Joohwan
  • 2,374
  • 1
  • 19
  • 30
  • 2
    Except that no major Python implementation performs, or will likely ever perform, tail recursion elimination. Also, those two functions can be merged into one using default arguments. –  Aug 26 '13 at 01:26