Python基础教程 递归式生成器

9.7.2 递归式生成器

前一节设计的生成器只能处理两层的嵌套列表，这是使用两个for循环来实现的。如果要处理任意层嵌套的列表，该如何办呢？例如，你可能使用这样的列表来表示树结构（也可以使用特定的树类，但策略是相同的）。对于每层嵌套，都需要一个for循环，但由于不知道有多少层嵌套，你必须修改解决方案，使其更灵活。该求助于递归了。

def flatten(nested):

try:

for sublist in nested:

for element in flatten(sublist):

yield element

except TypeError:

yield nested

调用flatten时，有两种可能性（处理递归时都如此）： 基线条件和递归条件。在基线条件下，要求这个函数展开单个元素（如一个数）。在这种情况下， for循环将引发TypeError异常（因为你试图迭代一个数），而这个生成器只生成一个元素。

然而，如果要展开的是一个列表（或其他任何可迭代对象），你就需要做些工作：遍历所有的子列表（其中有些可能并不是列表）并对它们调用flatten，然后使用另一个for循环生成展开后的子列表中的所有元素。这可能看起来有点不可思议，但确实可行。

>>> list(flatten([[[1], 2], 3, 4, [5, [6, 7]], 8]))

[1, 2, 3, 4, 5, 6, 7, 8]

然而，这个解决方案存在一个问题。如果nested是字符串或类似于字符串的对象，它就属于序列，因此不会引发TypeError异常，可你并不想对其进行迭代。

注意 在函数flatten中，不应该对类似于字符串的对象进行迭代，主要原因有两个。首先，你想将类似于字符串的对象视为原子值，而不是应该展开的序列。其次，对这样的对象进行迭代会导致无穷递归，因为字符串的第一个元素是一个长度为1的字符串，而长度为1的字符串的第一个元素是字符串本身！

要处理这种问题，必须在生成器开头进行检查。要检查对象是否类似于字符串，最简单、最快捷的方式是，尝试将对象与一个字符串拼接起来，并检查这是否会引发TypeError异常①。添加这种检查后的生成器如下：

def flatten(nested):

try:

# 不迭代类似于字符串的对象：

try: nested + ''

except TypeError: pass

else: raise TypeError

for sublist in nested:

for element in flatten(sublist):

yield element

except TypeError:

yield nested

如你所见，如果表达式nested + ''引发了TypeError异常，就忽略这种异常；如果没有引发TypeError异常，内部try语句中的else子句将引发TypeError异常，这样将在外部的excpet子句中原封不动地生成类似于字符串的对象。明白了吗？

下面的示例表明，这个版本也可用于字符串：

>>> list(flatten(['foo', ['bar', ['baz']]]))

['foo', 'bar', 'baz']

请注意，这里没有执行类型检查：我没有检查nested是否是字符串，而只是检查其行为是否类似于字符串，即能否与字符串拼接。对于这种检查，一种更自然的替代方案是，使用isinstance以及字符串和类似于字符串的对象的一些抽象超类，但遗憾的是没有这样的标准类。另外，即便是对UserString来说，也无法检查其类型是否为str。