Learning Python - Mark Lutz [261]
[1, [2, [3, 4], 5], 6, [7, 8]] # Arbitrarily nested sublists
Simple looping statements won’t work here because this not a linear iteration. Nested looping statements do not suffice either, because the sublists may be nested to arbitrary depth and in an arbitrary shape. Instead, the following code accommodates such general nesting by using recursion to visit sublists along the way:
def sumtree(L):
tot = 0
for x in L: # For each item at this level
if not isinstance(x, list):
tot += x # Add numbers directly
else:
tot += sumtree(x) # Recur for sublists
return tot
L = [1, [2, [3, 4], 5], 6, [7, 8]] # Arbitrary nesting
print(sumtree(L)) # Prints 36
# Pathological cases
print(sumtree([1, [2, [3, [4, [5]]]]])) # Prints 15 (right-heavy)
print(sumtree([[[[[1], 2], 3], 4], 5])) # Prints 15 (left-heavy)
Trace through the test cases at the bottom of this script to see how recursion traverses their nested lists. Although this example is artificial, it is representative of a larger class of programs; inheritance trees and module import chains, for example, can exhibit similarly general structures. In fact, we will use recursion again in such roles in more realistic examples later in this book:
In Chapter 24’s reloadall.py, to traverse import chains
In Chapter 28’s classtree.py, to traverse class inheritance trees
In Chapter 30’s lister.py, to traverse class inheritance trees again
Although you should generally prefer looping statements to recursion for linear iterations on the grounds of simplicity and efficiency, we’ll find that recursion is essential in scenarios like those in these later examples.
Moreover, you sometimes need to be aware of the potential of unintended recursion in your programs. As you’ll also see later in the book, some operator overloading methods in classes such as __setattr__ and __getattribute__ have the potential to recursively loop if used incorrectly. Recursion is a powerful tool, but it tends to be best when expected!
Function Objects: Attributes and Annotations
Python functions are more flexible than you might think. As we’ve seen in this part of the book, functions in Python are much more than code-generation specifications for a compiler—Python functions are full-blown objects, stored in pieces of memory all their own. As such, they can be freely passed around a program and called indirectly. They also support operations that have little to do with calls at all—attribute storage and annotation.
Indirect Function Calls
Because Python functions are objects, you can write programs that process them generically. Function objects may be assigned to other names, passed to other functions, embedded in data structures, returned from one function to another, and more, as if they were simple numbers or strings. Function objects also happen to support a special operation: they can be called by listing arguments in parentheses after a function expression. Still, functions belong to the same general category as other objects.
We’ve seen some of these generic use cases for functions in earlier examples, but a quick review helps to underscore the object model. For example, there’s really nothing special about the name used in a def statement: it’s just a variable assigned in the current scope, as if it had appeared on the left of an = sign. After a def runs, the function name is simply a reference to an object—you can reassign that object to other names freely and call it through any reference:
>>> def echo(message): # Name echo assigned to function object
... print(message)
...
>>> echo('Direct call') # Call object through original name
Direct call
>>> x = echo # Now x references the function too
>>> x('Indirect call!') # Call object through name by adding ()
Indirect