Handling Arbitrary Structures

On the other hand, recursion (or equivalent explicit stack-based algorithms, which we’ll finesse here) can be required to traverse arbitrarily shaped structures. As a simple example of recursion’s role in this context, consider the task of computing the sum of all the numbers in a nested sublists structure like this:

[1, [2, [3, 4], 5], 6, [7, 8]]                   # Arbitrarily nested sublists

广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元

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!