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

Question

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

if not ls: - What does it mean? As nothing has been specified, what is it looking for?
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:])?

1. See https://docs.python.org/3/library/stdtypes.html#truth-value-testing, it's the idiom for *"if `ls` is empty"*. 2. If you pass the whole list (`ls[0:]` or just `ls[:]`) into the recursive call, how will it ever become empty? — jonrsharpe, Apr 26 '16 at 07:42
@jonrsharpe thanks for the grammatical amendments and removing the `hard time` ;) — Andy K, Apr 26 '16 at 08:01

Tony Delroy · Accepted Answer · 2016-04-26T09:35:16.660

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] (in the other code below the if) and raise an exception; handling the empty list makes the function easier to use if listSum([]) returning 0 is sane for your application, but on the other hand having listSum([]) raise an exception might uncover bugs where lists are unexpectedly empty - you can decide which is more useful to you; happily if you do handle the empty-list case, len(ls) == 1 case then "just works" with the same recursion logic

Hi @tony-d, let's say I'm stupid and I want to keep carrying `listSum(ls[0]:)`, what would me prevent me in doing so? — Andy K, Apr 26 '16 at 07:46
@AndyK the system recursion limit? Again, if you're not shortening the list of each recursive call, you never reach the terminating condition of an empty list. — jonrsharpe, Apr 26 '16 at 07:47
Hi @AndyK - recursive calls do need some way to know when to stop, otherwise they'll either hang the program or crash when the stack is exhausted, as jonrsharpe mentions. — Tony Delroy, Apr 26 '16 at 07:48
@TonyD many thanks for your time and patience. You've totally nailed my questions. Kudos — Andy K, Apr 26 '16 at 08:00
@AndyK: you're welcome. Recursion does a lot of peoples' heads in - mine too at times - so if I save anyone a little grief, great. Cheers. — Tony Delroy, Apr 26 '16 at 08:02

1 Answers1