Andy K - 1 year ago 60
Python Question

# Why this way for the recursion and what does it mean?

I'm trying to understand this piece of code

``````def listSum(ls):
if not ls:
return 0

return ls[0] + listSum(ls[1:])
``````

Two things bug me a bit

1. `if not ls:`
- What does it mean? As nothing has been specified, what is it looking for?

2. `ls[0] + listSum(ls[1:])`
- I've tried using
`listSum(ls[0:])`
only and I have running error. Why? Why should I stick to
`ls[0] + listSum(ls[1:])`
?

Imagine it's called...

``````listSum([3, 5, 3, 7])
``````

It get down to...

``````return ls[0] + listSum(ls[1:])
``````

...which is evaluated as...

``````return 3 + listSum([5, 3, 7])
``````

Then `listSum([5, 3, 7])` as `5 + listsum([3, 7])`.

Then `listSum([3, 7])` as `3 + listsum([7])`.

Then `listSum([7])` as `7 + listsum([])`, which is where the `not ls` kicks in and returns `0`.

So, the complete thing is then evaluated as...

``````3 + 5 + 3 + 7 + 0
``````

Notes:

• `listSum(ls[1:])` is shortening the list each time - reducing the complexity of the remaining problem, until an invocation of `listSum` receives an empty list: the trivial case that `if not ls: return 0` handles

• recursive solutions are often made up of two parts: a solution for the simplest possible input (or sometimes, a couple very simple cases), and something saying how to take an arbitrarily complicated input and reduce it to a formula making one or more recusive calls that are each at least a little bit simpler, always moving towards that simplest possible input

• "I've tried using `listSum(ls[0:])`" - `ls[0:]` returns a copy of `ls` - it would ask for the same list to be processed ad infinitum

• it's arguably more intuitive to explicitly handle a list of one element - `if len(ls) == 1: return ls[0]` - but then if anyone called `listSum([])` you'd try to access `[0]` and raise an exception; handling the empty list makes the function safer to use (if "0" is meaningful as the sum of an empty list in your specific application), and happily the `len(ls) == 1` case then "just works"

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download