对象可以用其他对象作为属性值。当某个类的对象具有同一类的属性值时，它是递归对象。
2.9.1 链表类
本章前面介绍的链表是由第一个元素和链表的其余部分组成的。 链表的其余部分本身就是一个递归定义的链表。 空列表是没有第一个元素或rest的链表的一种特殊情况。 链表是一个序列：它有一个有限的长度，并支持通过索引选择元素。
现在我们可以实现具有相同行为的类。 在这个版本中，我们将使用特殊的方法名来定义它的行为，使我们的类可以使用Python中的内置len函数和元素选择操作符(方括号或operator.getitem)。 这些内置函数调用类的特殊方法名：长度由__len__计算，元素选择由__getitem__计算。 空链表由一个空元组表示，该元组长度为0，没有元素。
Copy >>> class Link:
"""A linked list with a first element and the rest."""
empty = ()
def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
self.first = first
self.rest = rest
def __getitem__(self, i):
if i == 0:
return self.first
else:
return self.rest[i-1]
def __len__(self):
return 1 + len(self.rest)
Copy >>> s = Link(3, Link(4, Link(5)))
>>> len(s)
3
>>> s[1]
4 __len__和__getitem__的定义实际上是递归的。当应用于用户定义的对象参数时，内置的Python函数len会调用一个名为__len__的方法。 同样，元素选择操作符调用一个名为__getitem__的方法。 因此，这两个方法的体将间接调用自己。 对于__len__，当self.rest的计算结果是空元组，Link.empty，长度为0。
内置的isinstance函数返回第一个实参的类型是第二个实参的类型还是继承自第二个实参的类型。 如果rest是一个Link实例或Link的某个子类的实例，则isinstance(rest, Link)为true。
我们的实现已经完成，但是目前很难检查Link类的实例。 为了帮助调试，我们还可以定义一个函数来将链接转换为字符串表达式。
Copy >>> def link_expression(s):
"""Return a string that would evaluate to s."""
if s.rest is Link.empty:
rest = ''
else:
rest = ', ' + link_expression(s.rest)
return 'Link({0}{1})'.format(s.first, rest)
Copy >>> link_expression(s)
'Link(3, Link(4, Link(5)))' 这种显示链接的方式非常方便，所以我们希望在显示链接实例时使用它。可以通过将linkexpression函数设置为特殊类属性__repr__的值来确保这种行为。Python通过调用用户定义类的__repr__方法来显示它们的实例。
Copy >>> Link.__repr__ = link_expression
>>> s
Link(3, Link(4, Link(5))) Link类有closure属性。就像列表的元素本身可以是列表一样，一个链接可以包含一个链接作为它的第一个元素。
Copy >>> s_first = Link(s, Link(6))
>>> s_first
Link(Link(3, Link(4, Link(5))), Link(6)) s_first链表只有两个元素，但是它的第一个元素是一个有三个元素的链表。
Copy >>> len(s_first)
2
>>> len(s_first[0])
3
>>> s_first[0][2]
5 递归函数特别适合操作链表。例如，递归的extend_link函数构建一个链表，其中包含一个链表实例s的元素，然后是另一个链表实例t的元素。将此函数作为Link类的__add__方法安装，可以模拟内置链表的添加行为。
Copy >>> def extend_link(s, t):
if s is Link.empty:
return t
else:
return Link(s.first, extend_link(s.rest, t))
>>> extend_link(s, s)
Link(3, Link(4, Link(5, Link(3, Link(4, Link(5))))))
>>> Link.__add__ = extend_link
>>> s + s
Link(3, Link(4, Link(5, Link(3, Link(4, Link(5)))))) 与列表推导式不同，一个链表可以使用两个高阶函数map_link和filter_link从另一个链表生成。下面定义的map_link函数将函数f应用于链表s的每个元素，并构造一个包含结果的链表。
Copy >>> def map_link(f, s):
if s is Link.empty:
return s
else:
return Link(f(s.first), map_link(f, s.rest))
>>> map_link(square, s)
Link(9, Link(16, Link(25))) filter_link函数的作用是：返回一个链表，该链表包含一个链表的所有元素，对于这个链表，f返回一个真值。map_link和filter_link的组合可以表达与列表推导相同的逻辑。
Copy >>> def filter_link(f, s):
if s is Link.empty:
return s
else:
filtered = filter_link(f, s.rest)
if f(s.first):
return Link(s.first, filtered)
else:
return filtered
>>> odd = lambda x: x % 2 == 1
>>> map_link(square, filter_link(odd, s))
Link(9, Link(25))
>>> [square(x) for x in [3, 4, 5] if odd(x)]
[9, 25] join_link函数递归地构造一个字符串，该字符串包含由分隔符字符串分隔的链表元素。结果比link_expression的输出要紧凑得多。
Copy >>> def join_link(s, separator):
if s is Link.empty:
return ""
elif s.rest is Link.empty:
return str(s.first)
else:
return str(s.first) + separator + join_link(s.rest, separator)
>>> join_link(s, ", ")
'3, 4, 5' 递归结构。 链表在递增构造序列时特别有用，这种情况在递归计算中经常出现。
第1章中的count_partitions函数通过树递归过程计算了使用最大大小为m的部分对整数n进行分区的方法数量。 有了序列，我们还可以使用类似的过程显式地枚举这些分区。
我们按照计数时所做的相同的递归分析来处理这个问题：用整数到m来划分n涉及到任何一个
对于基本情况，我们发现0有一个空分区，而分区一个负整数或使用小于1的部分是不可能的。
Copy >>> def partitions(n, m):
"""Return a linked list of partitions of n using parts of up to m.
Each partition is represented as a linked list.
"""
if n == 0:
return Link(Link.empty) # A list containing the empty partition
elif n < 0 or m == 0:
return Link.empty
else:
using_m = partitions(n-m, m)
with_m = map_link(lambda s: Link(m, s), using_m)
without_m = partitions(n, m-1)
return with_m + without_m 在递归情况下，我们构造了两个分区子列表。第一个使用m，因此我们在结果using_m的每个元素上加上m，形成with_m。
分区的结果是高度嵌套的：一个链表的链表。使用join_link和适当的分隔符，我们可以以人类可读的方式显示分区。
Copy >>> def print_partitions(n, m):
lists = partitions(n, m)
strings = map_link(lambda s: join_link(s, " + "), lists)
print(join_link(strings, "\n"))
Copy >>> print_partitions(6, 4)
4 + 2
4 + 1 + 1
3 + 3
3 + 2 + 1
3 + 1 + 1 + 1
2 + 2 + 2
2 + 2 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1 2.9.2 树类
树也可以用用户定义的类的实例来表示，而不是用内置序列类型的嵌套实例来表示。树是具有一系列同样是树的分支作为属性的任何数据结构。
内部值。 以前，我们定义树的方式是所有值都出现在树的叶子上。定义在每个子树的根具有内部值的树也很常见。内部值在树中称为label。下面的Tree类表示这样的树，其中每棵树都有一系列也是树的分支。
Copy >>> class Tree:
def __init__(self, label, branches=()):
self.label = label
for branch in branches:
assert isinstance(branch, Tree)
self.branches = branches
def __repr__(self):
if self.branches:
return 'Tree({0}, {1})'.format(self.label, repr(self.branches))
else:
return 'Tree({0})'.format(repr(self.label))
def is_leaf(self):
return not self.branches 例如，Tree类可以表示为递归实现fib(计算斐波那契数的函数)而在表达式树中计算的值。下面的函数fib_tree(n)返回一个以第n个斐波那契数字作为标签的树，并在其分支中跟踪先前计算的所有斐波那契数字。
Copy >>> def fib_tree(n):
if n == 1:
return Tree(0)
elif n == 2:
return Tree(1)
else:
left = fib_tree(n-2)
right = fib_tree(n-1)
return Tree(left.label + right.label, (left, right))
Copy >>> fib_tree(5)
Tree(3, (Tree(1, (Tree(0), Tree(1))), Tree(2, (Tree(1), Tree(1, (Tree(0), Tree(1))))))) 用这种方式表示的树也可以使用递归函数来处理。例如，我们可以对树的标签求和。作为基本情况，我们返回一个空分支没有标签。
Copy >>> def sum_labels(t):
"""Sum the labels of a Tree instance, which may be None."""
return t.label + sum([sum_labels(b) for b in t.branches])
Copy >>> sum_labels(fib_tree(5))
10 我们还可以应用memo来构造一个Fibonacci树，在Fibonacci树中，重复的子树仅由记忆版本fibon_tree创建一次，但可以多次作为不同更大树的分支使用。
Copy >>> fib_tree = memo(fib_tree)
>>> big_fib_tree = fib_tree(35)
>>> big_fib_tree.label
5702887
>>> big_fib_tree.branches[0] is big_fib_tree.branches[1].branches[1]
True
>>> sum_labels = memo(sum_labels)
>>> sum_labels(big_fib_tree)
142587180 在这些情况下，记忆法节省了大量的计算时间和内存。我们现在只创建35个不同的Tree类实例，而不是创建18,454,929个。
2.9.3 集
除了list、tuple和dictionary之外，Python还有第四个内置容器类型，称为set。集合字面值遵循用大括号括起来的元素的数学符号。重复的元素在解释时被移除。set是无序集合，因此打印的顺序可能与set字面量中的元素顺序不同。
Copy >>> s = {3, 2, 1, 4, 4}
>>> s
{1, 2, 3, 4} Python集合支持多种操作，包括成员资格测试、长度计算和标准集合操作的并集和交集
Copy >>> 3 in s
True
>>> len(s)
4
>>> s.union({1, 5})
{1, 2, 3, 4, 5}
>>> s.intersection({6, 5, 4, 3})
{3, 4} 除了并集和交集，Python集合还支持其他几种方法。 判断isdisjoint、issubset和issuerset提供集合比较。 集合是可变的，可以使用add、remove、discard和pop一次更改一个元素。 其他方法提供了多元素突变，如clear和update。 在本课程的这一点上，集合的Python文档 应该足够易懂，以填补细节。
实现集。 抽象地说，集合是支持成员测试、并、交和附加的不同对象的集合。 如果元素与集合相邻，则返回一个新集合，该新集合包含原集合的所有元素以及新元素(如果新元素是不同的)。 并集和交集分别返回出现在其中一个或两个集合中的元素集合。 与任何数据抽象一样，我们可以在提供此行为集合的任何集合表示上自由地实现任何函数。
在本节的其余部分中，我们将考虑实现集合的三种不同方法，这些集合的表示方式各不相同。 我们将通过分析集合运算的增长阶来刻画这些不同表示的效率。我们将使用本节前面介绍的Link和Tree类，它们为基本集合操作提供了简单而优雅的递归解决方案。
集合为无序序列。 表示一个集合的一种方法是将一个序列表示为一个元素只出现一次的序列。 空集合由空序列表示。 成员资格测试递归地遍历列表。
Copy >>> def empty(s):
return s is Link.empty
Copy >>> def set_contains(s, v):
"""Return True if and only if set s contains v."""
if empty(s):
return False
elif s.first == v:
return True
else:
return set_contains(s.rest, v)
Copy >>> s = Link(4, Link(1, Link(5)))
>>> set_contains(s, 2)
False
>>> set_contains(s, 5)
True set_contains的实现平均需要θ (n)时间来测试元素的隶属度，其中n是集合s的大小。使用这个线性时间函数，我们可以在线性时间内将一个元素邻接到集合中。
Copy >>> def adjoin_set(s, v):
"""Return a set containing all elements of s and element v."""
if set_contains(s, v):
return s
else:
return Link(v, s)
Copy >>> t = adjoin_set(s, 2)
>>> t
Link(2, Link(4, Link(1, Link(5))))
Copy >>> def intersect_set(set1, set2):
"""Return a set containing all elements common to set1 and set2."""
return keep_if_link(set1, lambda v: set_contains(set2, v))
Copy >>> intersect_set(t, apply_to_all_link(s, square))
Link(4, Link(1))
Copy >>> def union_set(set1, set2):
"""Return a set containing all elements either in set1 or set2."""
set1_not_set2 = keep_if_link(set1, lambda v: not set_contains(set2, v))
return extend_link(set1_not_set2, set2)
Copy >>> union_set(t, s)
Link(2, Link(4, Link(1, Link(5)))) 集合为有序序列。 加快集合操作速度的一种方法是改变集合元素的表示方式，使集合元素按递增的顺序列出。 要做到这一点，我们需要一些方法来比较两个对象，这样我们就能知道哪个更大。 在Python中，许多不同类型的对象都可以使用< 和> 运算符，但在本例中我们将集中讨论数字。 我们将以递增的顺序列出一组数字的元素来表示它。
有序的一个优点体现在set_contains中：在检查对象是否存在时，我们不再需要扫描整个集合。如果到达的集合元素大于要查找的元素，则知道该元素不在集合中
Copy >>> def set_contains(s, v):
if empty(s) or s.first > v:
return False
elif s.first == v:
return True
else:
return set_contains(s.rest, v)
Copy >>> u = Link(1, Link(4, Link(5)))
>>> set_contains(u, 0)
False
>>> set_contains(u, 4)
True 然而，假设e1小于e2。 由于e2小于set2的剩余元素，我们可以立即得出结论，e1不能出现在set2的剩余元素中的任何地方，因此不在交集中。 因此，我们不再需要考虑e1; 我们丢弃它，并继续处理set1的下一个元素。 当e2 < e1。 这是函数：
Copy >>> def intersect_set(set1, set2):
if empty(set1) or empty(set2):
return Link.empty
else:
e1, e2 = set1.first, set2.first
if e1 == e2:
return Link(e1, intersect_set(set1.rest, set2.rest))
elif e1 < e2:
return intersect_set(set1.rest, set2)
elif e2 < e1:
return intersect_set(set1, set2.rest)
Copy >>> intersect_set(s, s.rest)
Link(4, Link(5)) 以有序序列表示的集合的附加和并也可以在线性时间内计算。 这些实现留作练习。
集合作为二叉搜索树。 通过将集合元素排列成恰好有两个分支的树的形式，我们可以做得比有序列表更好。 树的根的入口保存着集合的一个元素。 左分支中的条目包括所有小于根分支的元素。 右分支中的元素包括所有大于根分支的元素。 下面的图显示了一些表示集合{1,3,5,7,9,11}的树。 同一个集合可以用树的多种不同方式表示。 在所有二叉搜索树中，左分支中的所有元素都小于根分支中的元素，而右子树中的所有元素都大于根分支中的元素。
Copy >>> def set_contains(s, v):
if s is None:
return False
elif s.entry == v:
return True
elif s.entry < v:
return set_contains(s.right, v)
elif s.entry > v:
return set_contains(s.left, v) 将一个项目与一个集合相连的实现类似，也需要θ (logn)步骤。为了附加一个值v，我们将v与entry进行比较，以确定v是应该添加到右分支还是左分支，并且在将v附加到适当的分支之后，我们将这个新构建的分支与原始条目和另一个分支拼接在一起。如果v等于元素，我们就返回节点。如果我们被要求将v附加到一棵空树上，我们生成了一棵以v为入口，并有空的左右分支的树。函数如下：
Copy >>> def adjoin_set(s, v):
if s is None:
return Tree(v)
elif s.entry == v:
return s
elif s.entry < v:
return Tree(s.entry, s.left, adjoin_set(s.right, v))
elif s.entry > v:
return Tree(s.entry, adjoin_set(s.left, v), s.right)
Copy >>> adjoin_set(adjoin_set(adjoin_set(None, 2), 3), 1)
Tree(2, Tree(1), Tree(3)) 我们声称搜索树可以在对数的步骤执行基于假设树是“平衡”，也就是说，每棵树的左和右子树有大约相同数量的元素，所以每个子树包含大约一半的元素。 但是我们怎么能确定我们建造的树是平衡的呢? 即使从平衡树开始，使用adjoin_set添加元素也可能产生不平衡的结果。 由于新添加元素的位置取决于该元素与集合中已有元素的比较方式，因此可以预期，如果我们“随机”添加元素，树将趋向于平均平衡。
但这并不是保证。 例如，如果我们从一个空集合开始，并以1到7的顺序邻接，我们最终会得到一个高度不平衡的树，其中所有的左子树都是空的，所以它没有一个简单有序列表的优势。 解决这个问题的一种方法是定义一个将任意树转换为具有相同元素的平衡树的操作。 我们可以在每隔几个adjoin_set操作后执行这个转换，以保持集合的平衡。 通过将树结构集转换为有序列表并返回，可以在线性时间内对它们执行交集和并集操作。 细节留作练习。
Python集合实现。 Python内置的set类型在内部不使用任何这些表示。 相反，Python使用了一种表示，该表示基于一种称为散列的技术，提供恒定时间的成员资格测试和毗连操作，这是另一门课程的主题。 内置Python集合不能包含可变数据类型，例如列表、字典或其他集合。 为了允许嵌套集合，Python还包括一个内置的不可变的frozenset类，它与set类共享方法，但排除了可变方法和操作符。
