Learning Python - Mark Lutz [260]
If this is difficult to understand (and it often is for new programmers), try adding a print of L to the function and run it again, to trace the current list at each call level:
>>> def mysum(L):
... print(L) # Trace recursive levels
... if not L: # L shorter at each level
... return 0
... else:
... return L[0] + mysum(L[1:])
...
>>> mysum([1, 2, 3, 4, 5])
[1, 2, 3, 4, 5]
[2, 3, 4, 5]
[3, 4, 5]
[4, 5]
[5]
[]
15
As you can see, the list to be summed grows smaller at each recursive level, until it becomes empty—the termination of the recursive loop. The sum is computed as the recursive calls unwind.
Coding Alternatives
Interestingly, we can also use Python’s if/else ternary expression (described in Chapter 12) to save some code real-estate here. We can also generalize for any summable type (which is easier if we assume at least one item in the input, as we did in Chapter 18’s minimum value example) and use Python 3.0’s extended sequence assignment to make the first/rest unpacking simpler (as covered in Chapter 11):
def mysum(L):
return 0 if not L else L[0] + mysum(L[1:]) # Use ternary expression
def mysum(L):
return L[0] if len(L) == 1 else L[0] + mysum(L[1:]) # Any type, assume one
def mysum(L):
first, *rest = L
return first if not rest else first + mysum(rest) # Use 3.0 ext seq assign
The latter two of these fail for empty lists but allow for sequences of any object type that supports +, not just numbers:
>>> mysum([1]) # mysum([]) fails in last 2
1
>>> mysum([1, 2, 3, 4, 5])
15
>>> mysum(('s', 'p', 'a', 'm')) # But various types now work
'spam'
>>> mysum(['spam', 'ham', 'eggs'])
'spamhameggs'
If you study these three variants, you’ll find that the latter two also work on a single string argument (e.g., mysum ('spam')), because strings are sequences of one-character strings; the third variant works on arbitary iterables, including open input files, but the others do not because they index; and the function header def mysum(first, * rest), although similar to the third variant, wouldn’t work at all, because it expects individual arguments, not a single iterable.
Keep in mind that recursion can be direct, as in the examples so far, or indirect, as in the following (a function that calls another function, which calls back to its caller). The net effect is the same, though there are two function calls at each level instead of one:
>>> def mysum(L):
... if not L: return 0
... return nonempty(L) # Call a function that calls me
...
>>> def nonempty(L):
... return L[0] + mysum(L[1:]) # Indirectly recursive
...
>>> mysum([1.1, 2.2, 3.3, 4.4])
11.0
Loop Statements Versus Recursion
Though recursion works for summing in the prior sections’ examples, it’s probably overkill in this context. In fact, recursion is not used nearly as often in Python as in more esoteric languages like Prolog or Lisp, because Python emphasizes simpler procedural statements like loops, which are usually more natural. The while, for example, often makes things a bit more concrete, and it doesn’t require that a function be defined to allow recursive calls:
>>> L = [1, 2, 3, 4, 5]
>>> sum = 0
>>> while L:
... sum += L[0]
... L = L[1:]
...
>>> sum
15
Better yet, for loops iterate for us automatically, making recursion largely extraneous in most cases (and, in all likelihood, less efficient in terms of memory space and execution time):
>>> L = [1, 2, 3, 4, 5]
>>> sum = 0
>>> for x in L: sum += x
...
>>> sum
15
With looping statements, we don’t require a fresh copy of a local scope on the call stack for each iteration, and we avoid the speed costs associated with function calls in general. (Stay tuned for Chapter 20’s timer case study for ways to compare the execution times of alternatives like these.)
Handling Arbitrary Structures
On the other hand, recursion