2.3 序列
INFO
序列（sequence）是有序的值集合。序列是计算机科学中一种强大而基础的抽象。序列并不是某个特定内置类型或抽象数据表示的实例，而是多种不同数据类型共有的一组行为。也就是说，序列有很多种，但它们都拥有共同的行为。具体来说：
- 长度（Length）：序列的长度是有限的，空序列的长度为 0
- 元素选择（Element selection）：序列拥有与每一个小于其长度的非负整数索引相对应的元素，索引从 0 开始表示第一个元素
Python 包含多种属于序列的原生数据类型，其中最重要的是列表（list）。
2.3.1 列表
列表值是一种长度任意的序列。列表有大量内置行为，也有表达这些行为的专门语法。我们已经见过列表字面量（求值为 list 实例），以及元素选择表达式（求值为列表中的某个值）。内置的 len 函数返回序列的长度。在下例中，digits 是一个包含四个元素的列表。索引 3 处的元素是 8。
>>> digits = [1, 8, 2, 8]
>>> len(digits)
4
>>> digits[3]
8此外，列表可以相加，也可以乘以整数。对序列来说，加法和乘法并不是把元素相加或相乘，而是把序列本身组合、复制。也就是说，operator 模块中的 add 函数（以及 + 运算符）会生成一个新列表，把相加的两个参数拼接起来。operator 中的 mul 函数（以及 * 运算符）接收一个列表和一个整数 k，返回由原列表重复 k 次构成的新列表。
>>> [2, 7] + digits * 2
[2, 7, 1, 8, 2, 8, 1, 8, 2, 8]列表中可以有任何值，包括另一个列表。要想选出嵌套列表里更深处的元素，可以把元素选择反复用几次。
>>> pairs = [[10, 20], [30, 40]]
>>> pairs[1]
[30, 40]
>>> pairs[1][0]
302.3.2 序列遍历
很多时候，我们想遍历序列的元素，依次对每个元素做点什么。这种模式太常见了，Python 专门提供了一条处理序列数据的控制语句：for 语句。
考虑这样一个问题：数出某个值在序列里出现了多少次。我们可以用 while 循环写一个函数来计算这个次数。
>>> def count(s, value):
"""统计 value 在序列 s 中出现的次数。"""
total, index = 0, 0
while index < len(s):
if s[index] == value:
total = total + 1
index = index + 1
return total
>>> count(digits, 8)
2Python 的 for 语句可以直接遍历元素值，从而简化这个函数体，根本不用引入 index 这个名称。
>>> def count(s, value):
"""统计在序列 s 中出现了多少次值为 value 的元素"""
total = 0
for elem in s:
if elem == value:
total = total + 1
return total
>>> count(digits, 8)
2for 语句由一个子句组成，形式如下：
for <name> in <expression>:
<suite>for 语句的执行过程如下：
- 求值头部（header）的
<expression>，它必须产生一个可迭代（iterable）值 - 对该可迭代值中的每个元素，按顺序执行：
- 在当前帧中将
<name>绑定到该值 - 执行语句组
<suite>
- 在当前帧中将
这个执行过程提到了可迭代值。列表是一种序列，而序列是可迭代值。它们的元素按顺序处理。Python 还包含其他可迭代类型，但我们目前先把重点放在序列上；「可迭代」一词的通用定义出现在第 4 章关于迭代器的部分。
这个求值过程有一个重要推论：for 语句执行完毕后，<name> 会绑定到序列的最后一个元素上。for 循环又给语句更新环境增加了一种方式。
序列解包（Sequence unpacking）。程序中一种常见的模式，是使用一个元素本身也是序列的序列，且所有内部序列长度固定。for 语句的头部可以包含多个名称，从而把每个元素序列「解包」到各自的元素中。例如，我们可能有一个由双元素列表组成的列表：
>>> pairs = [[1, 2], [2, 2], [2, 3], [4, 4]]并希望数出其中第一个元素和第二个元素相同的「对」有多少个。
>>> same_count = 0下面的 for 语句头部有两个名称，它们会分别绑定到每个「对」的第一个和第二个元素上。
>>> same_count = 0
>>> for x, y in pairs:
if x == y:
same_count = same_count + 1
>>> same_count
2把定长序列中的多个值绑定到多个名称，这种模式叫序列解包；它和我们在把多个值绑定到多个名称的赋值语句里见到的模式是一样的。
范围（Ranges）：range 是 Python 中另一种内置的序列类型，用于表示整数范围。范围用 range 创建，它接受两个整数参数：第一个是起始数字，第二个是目标范围末位数字的后一位。
>>> range(1, 10) # [1, 10)，包括 1，但不包括 10
range(1, 10)对范围调用 list 构造函数，会求值得到一个包含该范围所有元素的列表，这样就能方便地查看元素。
>>> list(range(5, 8))
[5, 6, 7]如果只给一个参数，它会被解释为从 0 开始的范围的结束值（后一位）。
>>> list(range(4))
[0, 1, 2, 3]范围常用作 for 头部的表达式，用来指定语句组应执行的次数。如果 for 头部中的名称在语句组里没用到，惯例是用单个下划线字符当名称：
>>> for _ in range(3):
print('Go Bears!')
Go Bears!
Go Bears!
Go Bears!对解释器来说，这个下划线只是环境中的另一个名称；但在程序员之间，它有约定俗成的含义，表示该名称不会出现在以后的任何表达式中。
2.3.3 序列处理
序列是如此常见的一种复合数据形式，以至于整个程序常常就围绕这一个抽象来组织。把序列当作输入和输出的模块化组件，可以随意混搭来完成数据处理。把一串简单、专一的序列处理操作串成流水线，就能定义出复杂的组件。
列表推导式（List Comprehensions）：许多序列处理操作都可以这样描述：对序列中的每个元素求值同一个固定表达式，把结果值收集到一个结果序列里。在 Python 中，列表推导式就是做这类计算的表达式。
>>> odds = [1, 3, 5, 7, 9]
>>> [x+1 for x in odds]
[2, 4, 6, 8, 10]上面的 for 关键字不是 for 语句的一部分，而是列表推导式的一部分，因为它被包在方括号里。子表达式 x+1 会在 x 依次绑定到 odds 的每个元素时求值，得到的值收集到一个列表中。
另一种常见的序列处理操作，是选出满足某些条件的值的子集。列表推导式也能表达这种模式，比如选出 odds 中所有能整除 25 的元素。
>>> [x for x in odds if 25 % x == 0]
[1, 5]列表推导式的一般形式是：
[<映射表达式> for <名称> in <序列表达式> if <过滤表达式>]要求值一个列表推导式，Python 先求值 <序列表达式>，它必须返回一个可迭代值。然后依次处理每个元素：把元素值绑定到 <名称>，求值过滤表达式，如果结果为真，就求值映射表达式。映射表达式的值收集到一个列表里。
聚合（Aggregation）：序列处理中第三种常见模式，是把序列里的所有值聚合为单个值。内置函数 sum、min 和 max 都是聚合函数的例子。
把「对每个元素求值一个表达式」「选出元素子集」「聚合元素」这几种模式组合起来，就能用序列处理的思路解决问题。
完全数（Perfect Number）是一个正整数，它等于所有因子之和。n 的因子是指小于 n 且能整除 n 的正整数。列出 n 的因子，可以用列表推导式表示。
>>> def divisors(n):
return [1] + [x for x in range(2, n) if n % x == 0]
>>> divisors(4)
[1, 2]
>>> divisors(12)
[1, 2, 3, 4, 6]有了 divisors，我们就能用另一个列表推导式算出 1 到 1000 之间的所有完全数。（通常认为 1 也是完全数，尽管按我们的 divisors 定义它并不符合。）
>>> [n for n in range(1, 1000) if sum(divisors(n)) == n]
[1, 6, 28, 496]我们还可以复用 divisors 的定义来解决另一个问题：给定面积，求整数边长矩形的最小周长。矩形的面积是宽乘以高。所以给定面积和高，就能算出宽。我们可以断言宽和高都能整除面积，以确保边长是整数。
>>> def width(area, height):
assert area % height == 0
return area // height矩形的周长是它各条边长之和。
>>> def perimeter(width, height):
return 2 * width + 2 * height整数边长的矩形，其高必定是面积的因子。把所有可能的高都考虑一遍，就能算出最小周长。
>>> def minimum_perimeter(area):
heights = divisors(area)
perimeters = [perimeter(width(area, h), h) for h in heights]
return min(perimeters)
>>> area = 80
>>> width(area, 5)
16
>>> perimeter(16, 5)
42
>>> perimeter(10, 8)
36
>>> minimum_perimeter(area)
36
>>> [minimum_perimeter(n) for n in range(1, 10)]
[4, 6, 8, 8, 12, 10, 16, 12, 12]高阶函数：我们在序列处理中观察到的这些常见模式，可以用高阶函数来表达。首先，「对序列中每个元素求值一个表达式」可以表示为把一个函数应用到每个元素上。
>>> def apply_to_all(map_fn, s):
return [map_fn(x) for x in s]「只保留某些表达式为真的元素」，也可以表示为对每个元素应用一个函数。
>>> def keep_if(filter_fn, s):
return [x for x in s if filter_fn(x)]最后，很多形式的聚合都可以表示为：把一个双参数函数反复应用到目前已经归约（reduced）的值和下一个元素上。
>>> def reduce(reduce_fn, s, initial):
reduced = initial
for x in s:
reduced = reduce_fn(reduced, x)
return reduced例如，可以用 reduce 把序列里所有元素乘在一起。用 mul 作 reduce_fn、1 作 initial，就能用它求出一串数字的乘积。
>>> reduce(mul, [2, 4, 8], 1)
64用这些高阶函数同样能找到完全数。
>>> def divisors_of(n):
divides_n = lambda x: n % x == 0
return [1] + keep_if(divides_n, range(2, n))
>>> divisors_of(12)
[1, 2, 3, 4, 6]
>>> from operator import add
>>> def sum_of_divisors(n):
return reduce(add, divisors_of(n), 0)
>>> def perfect(n):
return sum_of_divisors(n) == n
>>> keep_if(perfect, range(1, 1000))
[1, 6, 28, 496]惯用名称（Conventional Names）：在计算机科学界，apply_to_all 更常见的名字是 map（映射），keep_if 更常见的名字是 filter（过滤）。Python 内置的 map 和 filter 是这两个函数的泛化版本，它们不直接返回列表。这两个函数会在第 4 章讨论。上面的定义，等同于对内置 map 和 filter 调用的结果再调用 list 构造函数。
>>> apply_to_all = lambda map_fn, s: list(map(map_fn, s))
>>> keep_if = lambda filter_fn, s: list(filter(filter_fn, s))reduce 函数内置在 Python 标准库的 functools 模块里。在这个版本中，initial 参数是可选的。
>>> from functools import reduce
>>> from operator import mul
>>> def product(s):
return reduce(mul, s)
>>> product([1, 2, 3, 4, 5])
120在 Python 程序里，直接用列表推导式比用高阶函数更常见，但这两种序列处理方法都有人用。
2.3.4 序列抽象
我们已经介绍了两种满足序列抽象的原生数据类型：列表（list）和范围（range）。两者都满足本节开头提出的条件：长度和元素选择。Python 的序列类型还有另外两种行为，扩展了序列抽象。
成员资格（Membership）：我们可以测试一个值是否属于某个序列。Python 有 in 和 not in 两个运算符，根据元素是否出现在序列中，求值为 True 或 False。
>>> digits
[1, 8, 2, 8]
>>> 2 in digits
True
>>> 1828 not in digits
True切片（Slicing）：序列内部还含有更小的序列。序列的切片是原序列中任意一段连续的部分，用一对整数指定。和 range 构造函数一样，第一个整数是切片的起始索引，第二个是结束索引的后一位。
在 Python 中，序列切片的写法和元素选择类似，也用方括号。冒号分隔起始和结束索引。任意一端省略时，都默认取极值：起始索引默认是 0，结束索引默认是序列的长度。
>>> digits[0:2]
[1, 8]
>>> digits[1:]
[8, 2, 8]列举 Python 序列抽象这些额外行为，正好让我们想一想：一般来说，什么才算有用的数据抽象。抽象的丰富程度（也就是它包含多少行为）是有后果的。对抽象的使用者来说，额外的行为可能很有帮助。但另一方面，用一个新的数据类型去满足丰富抽象的全部要求，可能相当困难。丰富抽象还有一个坏处：使用者要花更长时间去学。
序列之所以有如此丰富的抽象，是因为它们在计算中无处不在，学这少量复杂行为是值得的。一般来说，大多数用户定义的抽象都应该尽量简单。
拓展材料：切片符号支持多种特殊情况，例如负的起始值、结束值和步长。在线书籍《Dive Into Python 3》中名为 列表切片 的小节给出了完整的描述。本章我们只会用到上面这些基本特性。
2.3.5 字符串
文本值对计算机科学来说，也许比数字还要基础。一个恰当的例证是：Python 程序本身就是以文本形式编写和保存的。Python 里表示文本的原生数据类型叫字符串（string），对应构造函数 str。
Python 中字符串如何表示、如何书写、如何操作，细节很多。字符串是丰富抽象的又一个例子，程序员得下不少功夫才能掌握。本节只是对字符串核心行为的简要介绍。
字符串字面量（string literals）能表示任意文本，用单引号或双引号括起来。
>>> 'I am string!'
'I am string!'
>>> "I've got an apostrophe"
"I've got an apostrophe"
>>> '您好'
'您好'我们在之前的代码里已经见过字符串：文档字符串（docstrings）、print 调用中的文本，以及 assert 语句中的错误消息。
字符串满足本节开头介绍的序列两个基本条件：有长度，也支持元素选择。
>>> city = 'Berkeley'
>>> len(city)
8
>>> city[3]
'k'字符串的元素本身就是只含单个字符的字符串。字符可以是字母表里的任意单个字母、标点符号或其他符号。和许多其他编程语言不同，Python 没有单独的字符类型：任何文本都是字符串，表示单个字符的字符串长度为 1。
和列表一样，字符串也能通过加法和乘法组合。
>>> 'Berkeley' + ', CA'
'Berkeley, CA'
>>> 'Shabu ' * 2
'Shabu Shabu '成员资格：字符串的行为和其他序列类型不一样。字符串抽象并不完全符合我们为列表和范围描述的通用序列抽象。特别是，成员运算符 in 虽然适用于字符串，但行为和应用于序列时完全不同：它匹配的是子串，而不是元素。
>>> 'here' in "Where's Waldo?"
True多行字面量（Multiline Literals）：字符串不限于一行。三引号可以界定跨多行的字符串字面量。我们在文档字符串里已经大量用过这种三引号。
>>> """The Zen of Python
claims, Readability counts.
Read more: import this."""
'The Zen of Python\nclaims, "Readability counts."\nRead more: import this.'在上面的打印结果中，\n（读作「backslash en」）是代表换行符的单个元素。虽然它看起来像两个字符（反斜杠和「n」），但计算长度和做元素选择时，它都算作单个字符。
字符串强制转换（String Coercion）：在 Python 里，只要调用 str 构造函数、把一个对象值当作参数传进去，就能从任何对象造出一个字符串。字符串的这个特性，很适合从各种类型的对象拼出描述性的字符串。
>>> str(2) + ' is an element of ' + str(digits)
'2 is an element of [1, 8, 2, 8]'拓展材料：计算机中的文本编码是个复杂的话题。本章我们会忽略字符串底层表示的细节。不过对很多应用来说，了解计算机如何编码字符串的细节是必备知识。《Dive Into Python 3》的 字符串章节 介绍了字符编码和 Unicode。
2.3.6 树
我们能够把列表用作其他列表的元素，这给编程语言提供了一种新的组合手段。这种能力称为数据类型的闭包性质（closure property）。一般来说，如果一种组合数据值的方法，其结果本身还能用同样的方法继续组合，那么这种方法就具有闭包性质。闭包是任何组合手段之所以强大的关键，因为它让我们能构造层次结构（hierarchical structures）—— 由部分组成的结构，而每个部分本身又由更小的部分组成，依此类推。
我们可以用箱式指针（box-and-pointer）记法在环境图中可视化列表。列表画成一排相邻的方框，里面装着列表的元素。数字、字符串、布尔值和 None 这类基本值直接写在元素框里。函数值和其他列表这类复合值，则用箭头表示。
在列表里嵌套列表会引入复杂性。树（Tree）是一种基础的数据抽象，它给层次化数据的组织和操作带来了规律。
树有一个根标签（root label）和一个分支（branches）序列。树的每个分支本身也是一棵树。没有分支的树称为叶子（leaf）。树内部包含的任何树，都叫这棵树的子树（sub-tree，比如分支的分支）。每棵子树的根，都是这棵树里的一个节点（node）。
树的数据抽象由构造函数 tree 和选择函数 label、branches 组成。我们先从简化版本开始。
>>> def tree(root_label, branches=[]):
for branch in branches:
assert is_tree(branch), '分支必须是树'
return [root_label] + list(branches)
>>> def label(tree):
return tree[0]
>>> def branches(tree):
return tree[1:]只有当一棵树有根标签，且所有分支也都是树时，它才是结构良好（well-formed）的。tree 构造函数里用 is_tree 来验证所有分支是否结构良好。
>>> def is_tree(tree):
if type(tree) != list or len(tree) < 1:
return False
for branch in branches(tree):
if not is_tree(branch):
return False
return Trueis_leaf 函数检查树有没有分支。
>>> def is_leaf(tree):
return not branches(tree)树可以用嵌套表达式构造。下面这棵树 t 的根标签是 3，有两个分支。
>>> t = tree(3, [tree(1), tree(2, [tree(1), tree(1)])])
>>> t
[3, [1], [2, [1], [1]]]
>>> label(t)
3
>>> branches(t)
[[1], [2, [1], [1]]]
>>> label(branches(t)[1])
2
>>> is_leaf(t)
False
>>> is_leaf(branches(t)[0])
True树形递归函数可以用来构造树。例如，第 n 棵斐波那契树的根标签是第 n 个斐波那契数；当 n > 1 时，它有两个分支，而这两个分支也都是斐波那契树。斐波那契树直观地展示了斐波那契数的树形递归计算过程。
>>> def fib_tree(n):
if n == 0 or n == 1:
return tree(n)
else:
left, right = fib_tree(n-2), fib_tree(n-1)
fib_n = label(left) + label(right)
return tree(fib_n, [left, right])
>>> fib_tree(5)
[5, [2, [1], [1, [0], [1]]], [3, [1, [0], [1]], [2, [1], [1, [0], [1]]]]]树形递归函数也可以用来处理树。例如，count_leaves 函数用来数一棵树的叶子数。
>>> def count_leaves(tree):
if is_leaf(tree):
return 1
else:
branch_counts = [count_leaves(b) for b in branches(tree)]
return sum(branch_counts)
>>> count_leaves(fib_tree(5))
8分割树（Partition trees）：树也可以用来表示整数的分割。用最大为 m 的部分分割 n，对应的分割树是一棵二叉（两个分支）树，代表计算过程中所做的选择。在一棵非叶子的分割树中：
- 左分支（索引 0）包含所有至少用一个 m 来分割 n 的方式，
- 右分支（索引 1）包含用最大为 m-1 的部分得到的分割，以及
- 根标签是 m。
分割树叶子的标签，表示从树根到叶子的这条路径是否代表 n 的一次成功分割。
>>> def partition_tree(n, m):
"""返回一棵使用最大为 m 的部分分割 n 的分割树"""
if n == 0:
return tree(True)
elif n < 0 or m == 0:
return tree(False)
else:
left = partition_tree(n-m, m)
right = partition_tree(n, m-1)
return tree(m, [left, right])
>>> partition_tree(2, 2)
[2, [True], [1, [1, [True], [False]], [False]]]从分割树打印分割结果，是另一个遍历树的树形递归过程，它把每个分割构造成一个列表。每当遇到一个 True 叶子，就打印对应的分割。
>>> def print_parts(tree, partition=[]):
if is_leaf(tree):
if label(tree):
print(' + '.join(partition))
else:
left, right = branches(tree)
m = str(label(tree))
print_parts(left, partition + [m])
print_parts(right, partition)
>>> print_parts(partition_tree(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切片操作也可以用在树的分支上。例如，我们可能想限制一棵树的分支数量。二叉树要么是叶子，要么是至多两棵二叉树组成的序列。一种常见的树变换叫二叉化（binarization），它把相邻的分支归并到一起，从原树算出一棵二叉树。
>>> def right_binarize(tree):
"""构造一棵右分叉的二叉树"""
if is_leaf(tree):
return tree
if len(tree) > 2:
tree = [tree[0], tree[1:]]
return [right_binarize(b) for b in tree]
>>> right_binarize([1, 2, 3, 4, 5, 6, 7])
[1, [2, [3, [4, [5, [6, 7]]]]]]2.3.7 链表
到目前为止，我们只用原生类型来表示序列。然而，我们也可以开发并非 Python 内置的序列表示形式。一种常见的序列表示用嵌套的「对」构造，称为链表（linked list）。下面的环境图展示了包含 1、2、3、4 的四元素序列的链表表示。
链表是一个「对」，里面装着序列的第一个元素（本例中是 1）和序列的其余部分（本例中是 2、3、4 的表示）。第二个元素本身也是一个链表。最内层那个只含 4 的链表，其余部分是 'empty'，一个表示空链表的值。
链表具有递归结构：链表的其余部分要么是链表，要么是 'empty'。我们可以定义一个抽象数据表示，用来验证、构造和选择链表的各个组件。
>>> empty = 'empty'
>>> def is_link(s):
"""判断 s 是否为链表"""
return s == empty or (len(s) == 2 and is_link(s[1]))
>>> def link(first, rest):
"""用 first 和 rest 构建一个链表"""
assert is_link(rest), " rest 必须是一个链表"
return [first, rest]
>>> def first(s):
"""返回链表 s 的第一个元素"""
assert is_link(s), " first 只能用于链表"
assert s != empty, "空链表没有第一个元素"
return s[0]
>>> def rest(s):
"""返回 s 的剩余元素"""
assert is_link(s), " rest 只能用于链表"
assert s != empty, "空链表没有剩余元素"
return s[1]在上面，link 是构造函数，first 和 rest 是链表抽象数据表示的选择函数。链表的行为条件是：和「对」一样，它的构造函数和选择函数互为逆函数。
- 如果链表
s由第一个元素f和链表r构造而成，那么first(s)返回f，rest(s)返回r。
我们可以用构造函数和选择函数来操作链表。
>>> four = link(1, link(2, link(3, link(4, empty))))
>>> first(four)
1
>>> rest(four)
[2, [3, [4, 'empty']]]我们对这类抽象数据的实现，用的是作为双元素 list 值的「对」。值得一提的是，我们之前也能用函数实现「对」，而且可以用任意「对」来实现链表，因此只用函数也能实现链表。
链表可以按顺序存储一系列值，但我们还没证明它满足序列抽象。利用我们定义的抽象数据表示，可以实现表征序列的两个行为：长度和元素选择。
>>> def len_link(s):
"""返回链表 s 的长度"""
length = 0
while s != empty:
s, length = rest(s), length + 1
return length
>>> def getitem_link(s, i):
"""返回链表 s 中索引为 i 的元素"""
while i > 0:
s, i = rest(s), i - 1
return first(s)现在，我们可以用这些函数把链表当作序列来操作。（我们还不能使用内置的 len 函数、元素选择语法或 for 语句，但很快就行了。）
>>> len_link(four)
4
>>> getitem_link(four, 1)
2下面这一系列环境图，展示了 getitem_link 在链表中查找索引为 1 的元素 2 的迭代过程。为了简化图示，下面我们用 Python 原语来定义链表 four。这个实现选择打破了抽象屏障，但能让我们在这个例子里更方便地查看计算过程。
首先调用函数 getitem_link，创建一个局部帧。
while 头部的表达式求值为 True，于是执行 while 语句组里的赋值语句。函数 rest 返回以 2 开头的子列表。
接下来，局部名称 s 会更新为指向以原列表第二个元素开头的子列表。此时 while 头部表达式求值为假，于是 Python 会求值 getitem_link 最后一行 return 语句里的表达式。
最后这张环境图显示了调用 first 时的局部帧，里面有个名称 s 绑定到同一个子列表。first 函数取出值 2 并返回，这个值也会从 getitem_link 返回。
这个例子展示了链表计算中一种常见的模式：迭代的每一步都作用在原列表越来越短的后缀上。这种逐步求出长度和元素的增量处理，确实要花一些计算时间。Python 内置的序列类型采用了不同的实现方式，求序列长度或取元素时不会有这么大的开销。这种表示的细节超出了本书的范围。
递归操作（Recursive manipulation）：len_link 和 getitem_link 都是迭代式的。它们逐层剥开嵌套的「对」，直到到达列表末尾（len_link）或目标元素（getitem_link）。我们也可以用递归来实现长度计算和元素选择。
>>> def len_link_recursive(s):
"""返回链表 s 的长度"""
if s == empty:
return 0
return 1 + len_link_recursive(rest(s))
>>> def getitem_link_recursive(s, i):
"""返回链表 s 中索引为 i 的元素"""
if i == 0:
return first(s)
return getitem_link_recursive(rest(s), i - 1)
>>> len_link_recursive(four)
4
>>> getitem_link_recursive(four, 1)
2这些递归实现沿着「对」链往下走，直到到达列表末尾（len_link_recursive）或目标元素（getitem_link_recursive）。
递归对于转换和组合链表也很有用。
>>> def extend_link(s, t):
"""返回一个在 s 链表的末尾连接 t 链表后的延长链表"""
assert is_link(s) and is_link(t)
if s == empty:
return t
else:
return link(first(s), extend_link(rest(s), t))
>>> extend_link(four, four)
[1, [2, [3, [4, [1, [2, [3, [4, 'empty']]]]]]]]
>>> def apply_to_all_link(f, s):
"""应用 f 到 s 中的每个元素"""
assert is_link(s)
if s == empty:
return s
else:
return link(f(first(s)), apply_to_all_link(f, rest(s)))
>>> apply_to_all_link(lambda x: x*x, four)
[1, [4, [9, [16, 'empty']]]]
>>> def keep_if_link(f, s):
"""返回 s 中 f(e) 为 True 的元素"""
assert is_link(s)
if s == empty:
return s
else:
kept = keep_if_link(f, rest(s))
if f(first(s)):
return link(first(s), kept)
else:
return kept
>>> keep_if_link(lambda x: x%2 == 0, four)
[2, [4, 'empty']]
>>> def join_link(s, separator):
"""返回由 separator 分隔的 s 中的所有元素组成的字符串"""
if s == empty:
return ""
elif rest(s) == empty:
return str(first(s))
else:
return str(first(s)) + separator + join_link(rest(s), separator)
>>> join_link(four, ", ")
'1, 2, 3, 4'递归构造（Recursive Construction）：当序列需要增量式地构造时，链表特别有用，而这种情况在递归计算中经常出现。
第一章的 count_partitions 函数通过树形递归过程，计算了用最大为 m 的部分分割整数 n 的方法数。有了序列，我们也可以用类似的过程把这些分割显式地枚举出来。
我们沿用计数时对问题的递归分析：用最大为 m 的整数分割 n，只有两种情况：
- 用最大为 m 的整数分割 n-m，或者
- 用最大为 m-1 的整数分割 n
至于基准情况：0 有一个空分割，而分割负整数、或者用小于 1 的部分，都是不可能的。
>>> def partitions(n, m):
"""返回一个链表，包含使用最大为 m 的部分对 n 的分割。
每个分割都表示为一个链表
"""
if n == 0:
return link(empty, empty) # 一个包含空分割的链表
elif n < 0 or m == 0:
return empty
else:
using_m = partitions(n-m, m)
with_m = apply_to_all_link(lambda s: link(m, s), using_m)
without_m = partitions(n, m-1)
return extend_link(with_m, without_m)在递归情况里，我们构造两个分割子列表。第一个用到 m，所以我们在 using_m 结果的每个元素前面加上 m，构成 with_m。
partitions 的结果嵌套很深：它是链表的链表，而每个链表又表示为 list 值的嵌套对。配合合适的分隔符调用 join_link，我们就能以方便人阅读的方式把这些分割显示出来。
>>> def print_partitions(n, m):
lists = partitions(n, m)
strings = apply_to_all_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