2.9 递归对象

对象可以用其他对象作为属性值。当某个类的对象具有同一类的属性值时，它是递归对象。

2.9.1 链表类

本章前面介绍的链表是由第一个元素和链表的其余部分组成的。 链表的其余部分本身就是一个递归定义的链表。 空列表是没有第一个元素或rest的链表的一种特殊情况。 链表是一个序列：它有一个有限的长度，并支持通过索引选择元素。

现在我们可以实现具有相同行为的类。 在这个版本中，我们将使用特殊的方法名来定义它的行为，使我们的类可以使用Python中的内置len函数和元素选择操作符(方括号或operator.getitem)。 这些内置函数调用类的特殊方法名：长度由__len__计算，元素选择由__getitem__计算。 空链表由一个空元组表示，该元组长度为0，没有元素。

>>> 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)

>>> 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类的实例。 为了帮助调试，我们还可以定义一个函数来将链接转换为字符串表达式。

>>> 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)

>>> link_expression(s)
'Link(3, Link(4, Link(5)))'

这种显示链接的方式非常方便，所以我们希望在显示链接实例时使用它。可以通过将linkexpression函数设置为特殊类属性__repr__的值来确保这种行为。Python通过调用用户定义类的__repr__方法来显示它们的实例。

>>> Link.__repr__ = link_expression
>>> s
Link(3, Link(4, Link(5)))

Link类有closure属性。就像列表的元素本身可以是列表一样，一个链接可以包含一个链接作为它的第一个元素。

>>> s_first = Link(s, Link(6))
>>> s_first
Link(Link(3, Link(4, Link(5))), Link(6))

s_first链表只有两个元素，但是它的第一个元素是一个有三个元素的链表。

>>> len(s_first)
2
>>> len(s_first[0])
3
>>> s_first[0][2]
5

递归函数特别适合操作链表。例如，递归的extend_link函数构建一个链表，其中包含一个链表实例s的元素，然后是另一个链表实例t的元素。将此函数作为Link类的__add__方法安装，可以模拟内置链表的添加行为。

>>> 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的每个元素，并构造一个包含结果的链表。

>>> 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的组合可以表达与列表推导相同的逻辑。

>>> 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的输出要紧凑得多。

>>> 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涉及到任何一个

1. 用整数进行n-m的分区，

2. 或者用整数进行n- 1的分区。

对于基本情况，我们发现0有一个空分区，而分区一个负整数或使用小于1的部分是不可能的。

>>> 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和适当的分隔符，我们可以以人类可读的方式显示分区。

>>> def print_partitions(n, m):
        lists = partitions(n, m)
        strings = map_link(lambda s: join_link(s, " + "), lists)
        print(join_link(strings, "\n"))

>>> 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类表示这样的树，其中每棵树都有一系列也是树的分支。

>>> 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个斐波那契数字作为标签的树，并在其分支中跟踪先前计算的所有斐波那契数字。

>>> 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))

>>> fib_tree(5)
Tree(3, (Tree(1, (Tree(0), Tree(1))), Tree(2, (Tree(1), Tree(1, (Tree(0), Tree(1)))))))

用这种方式表示的树也可以使用递归函数来处理。例如，我们可以对树的标签求和。作为基本情况，我们返回一个空分支没有标签。

>>> 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])

>>> sum_labels(fib_tree(5))
10

我们还可以应用memo来构造一个Fibonacci树，在Fibonacci树中，重复的子树仅由记忆版本fibon_tree创建一次，但可以多次作为不同更大树的分支使用。

>>> 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字面量中的元素顺序不同。

>>> s = {3, 2, 1, 4, 4}
>>> s
{1, 2, 3, 4}

Python集合支持多种操作，包括成员资格测试、长度计算和标准集合操作的并集和交集

>>> 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类，它们为基本集合操作提供了简单而优雅的递归解决方案。

集合为无序序列。 表示一个集合的一种方法是将一个序列表示为一个元素只出现一次的序列。 空集合由空序列表示。 成员资格测试递归地遍历列表。

>>> def empty(s):
        return s is Link.empty

>>> 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)

>>> s = Link(4, Link(1, Link(5)))
>>> set_contains(s, 2)
False
>>> set_contains(s, 5)
True

set_contains的实现平均需要θ (n)时间来测试元素的隶属度，其中n是集合s的大小。使用这个线性时间函数，我们可以在线性时间内将一个元素邻接到集合中。

>>> 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)

>>> t = adjoin_set(s, 2)
>>> t
Link(2, Link(4, Link(1, Link(5))))

在设计一个表现形式时，我们应该关注的一个问题是效率。相交两个集合set1和set2也需要隶属度测试，但这次set1的每个元素必须测试set2的隶属度，导致步长为n的两个集合的二次阶增长，$\theta(n^2)$。

>>> 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))

>>> intersect_set(t, apply_to_all_link(s, square))
Link(4, Link(1))

在计算两个集合的并集时，必须注意不要将任何元素包含两次。union_set函数还需要一个线性数量的成员资格测试，创建一个过程，也包括$\theta(n^2)$步骤。

>>> 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)

>>> union_set(t, s)
Link(2, Link(4, Link(1, Link(5))))

集合为有序序列。 加快集合操作速度的一种方法是改变集合元素的表示方式，使集合元素按递增的顺序列出。 要做到这一点，我们需要一些方法来比较两个对象，这样我们就能知道哪个更大。 在Python中，许多不同类型的对象都可以使用< 和> 运算符，但在本例中我们将集中讨论数字。 我们将以递增的顺序列出一组数字的元素来表示它。

有序的一个优点体现在set_contains中：在检查对象是否存在时，我们不再需要扫描整个集合。如果到达的集合元素大于要查找的元素，则知道该元素不在集合中

>>> 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)

>>> u = Link(1, Link(4, Link(5)))
>>> set_contains(u, 0)
False
>>> set_contains(u, 4)
True

这样可以节省多少步骤? 在最坏的情况下，我们正在寻找的项可能是集合中最大的项，因此步数与无序表示相同。 另一方面，如果我们搜索许多不同大小的条目，我们可以预期，有时我们可以在靠近列表开始的地方停止搜索，而有时我们仍然需要检查列表的大部分内容。 平均来说，我们应该需要检查集合中大约一半的项。 因此，所需的平均步数大约是$\frac{n}{2}$ 。 这仍然是θ (n)增长，但它节省了我们在实践中比以前的实现一些时间。

我们可以通过重新实现intersect_set获得更令人印象深刻的加速。 在无序表示中，这个操作需要$\theta(n^2)$步，因为我们对set1的每个元素都进行了完整的扫描。 但是对于有序表示，我们可以使用更聪明的方法。 我们同时遍历这两个集合，跟踪set1中的元素e1和set2中的元素e2。 当e1和e2相等时，我们把那个元素包含在交集中。

然而，假设e1小于e2。 由于e2小于set2的剩余元素，我们可以立即得出结论，e1不能出现在set2的剩余元素中的任何地方，因此不在交集中。 因此，我们不再需要考虑e1; 我们丢弃它，并继续处理set1的下一个元素。 当e2 < e1。 这是函数：

>>> 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)

>>> intersect_set(s, s.rest)
Link(4, Link(5))

要估计这个过程所需的步骤数，请注意，在每一步中，我们都会缩小至少一个集合的大小。 因此，所需的步数最多是set1和set2大小的总和，而不是像无序表示那样是大小的乘积。 这是θ (n)增长，而不是$\Theta(n^2)$增长，这是一个相当大的加速，即使对于中等大小的组。 例如，两组大小为100的交集大约需要200步，而非无序表示的10,000步。

以有序序列表示的集合的附加和并也可以在线性时间内计算。 这些实现留作练习。

集合作为二叉搜索树。 通过将集合元素排列成恰好有两个分支的树的形式，我们可以做得比有序列表更好。 树的根的入口保存着集合的一个元素。 左分支中的条目包括所有小于根分支的元素。 右分支中的元素包括所有大于根分支的元素。 下面的图显示了一些表示集合{1,3,5,7,9,11}的树。 同一个集合可以用树的多种不同方式表示。 在所有二叉搜索树中，左分支中的所有元素都小于根分支中的元素，而右子树中的所有元素都大于根分支中的元素。

树形表示的优点是这样的：假设我们想要检查一个值v是否包含在一个集合中。 我们从比较v和entry开始。 如果v小于这个，我们知道我们只需要搜索左边的子树; 如果v更大，我们只需要搜索右边的子树。 现在，如果这棵树是“平衡的”，那么每一个子树的大小都是原来的一半左右。 因此，在一个步骤中，我们将搜索大小为n的树的问题简化为搜索大小为$\frac{n}{2}$的树。 由于树的大小在每一步中减半，我们可以预期搜索树所需的步数增长为θ (logn)。 对于大集合，这将比以前的表示有显著的加速。 这个set_contains函数利用了树结构集的排序结构。

>>> 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为入口，并有空的左右分支的树。函数如下：

>>> 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)

>>> 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类共享方法，但排除了可变方法和操作符。