>>> from env_helper import info; info()
页面更新时间: 2020-08-26 21:25:44
操作系统/OS: Linux-4.19.0-10-amd64-x86_64-with-debian-10.5 ;Python: 3.7.3
8.6. 递归¶
程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。下面是一个递归式函数定义:
>>> def recursion():
>>> return recursion()
如果你运行它,结果将如何呢? 你将发现运行一段时间后,这个程序崩溃了(引发异常)。 从理论上说,这个程序将不断运行下去,但每次调用函数时,都将消耗一些内存。 因此函数调用次数达到一定的程度(且之前的函数 调用未返回)后,将耗尽所有的内存空间,导致程序终止并显示错误消息“超过最大递归深度”。
这个函数中的递归称为无穷递归,因为它从理论上说永远不会结束。 你想要的是能对你有所帮助的递归函 数,这样的递归函数通常包含下面两部分。
基线条件(针对最小的问题):满足这种条件时函数将直接返回一个值。
递归条件:包含一个或多个调用,这些调用旨在解决问题的一部分。
这里的关键是,通过将问题分解为较小的部分,可避免递归没完没了,因为问题终将被分解成基线条件可以解决的最小问题。
那么如何让函数调用自身呢?这没有看起来那么难懂。前面说过,每次调用函数时,都将为此创建一个新的命名空间。 这意味着函数调用自身时,是两个不同的函数[更准确地说,是不同版本(即命名空间不同)的同一个函数]在交流。 你可将此视为两个属于相同物种的动物在彼此交流。
8.6.1. 两个经典案例:阶乘和幂¶
本节探讨两个经典的递归函数。首先,假设你要计算数字n的阶乘。 n的阶乘为 n
× (n-1) × (n -2) × … × 1 ,在数学领域的用途非常广泛。 例如,计算将 n
个人排成一队有多少种方式。如何计算阶乘呢?可使用循环。
>>> def factorial(n):
>>> result = n
>>> for i in range(1, n):
>>> result *= i
>>> return result
这种实现可行,而且直截了当。大致而言,它是这样做的:首先将result设置为n,再将其 依次乘以1到n-1的每个数字,最后返回result。但如果你愿意,可采取不同的做法。关键在于阶 乘的数学定义,可表述如下。
1的阶乘为1。
对于大于1的数字n,其阶乘为n-1的阶乘再乘以n。
如你所见,这个定义与本节开头的定义完全等价。
下面来考虑如何使用函数来实现这个定义。理解这个定义后,实现起来其实非常简单。
>>> def factorial(n):
>>> if n == 1:
>>> return 1
>>> else:
>>> return n * factorial(n - 1)
这是前述定义的直接实现,只是别忘了函数调用factorial(n)和factorial(n – 1)是不同的实体。
再来看一个示例。假设你要计算幂,就像内置函数pow和运算符**所做的那样。要定义一 个数字的整数次幂,有多种方式,但先来看一个简单的定义:power(x, n)(x的n次幂)是将数 字x自乘n - 1次的结果,即将n个x相乘的结果。换而言之,power(2, 3)是2自乘两次的结果, 即2 × 2 × 2 = 8。
这实现起来很容易。
>>> def power(x, n):
>>> result = 1
>>> for i in range(n):
>>> result *= x
>>> return result
这是一个非常简单的小型函数,但也可将定义修改成递归式的。
对于任何数字x,power(x, 0)都为1。
n>0时,power(x, n)为power(x, n-1)与x的乘积。
如你所见,这种定义提供的结果与更简单的迭代定义完全相同。理解定义是最难的,而实现起来很容易。
>>> def power(x, n):
>>> if n == 0:
>>> return 1
>>> else:
>>> return x * power(x, n - 1)
我再次将定义从较为正规的文字描述转换成了编程语言(Python)。
提示 如果函数或算法复杂难懂,在实现前用自己的话进行明确的定义将大有裨益。以这种“准 编程语言”编写的程序通常称为伪代码。
在很多情况下,使用递归的可读性更高,且有时要高得多,在你理解了函数的递归式定义时尤其如此。另外,虽然你完全能够避免编写递归函数,但作为程序员,你必须能够读懂其他人编写的递归算法和函数。
8.6.2. 另一个经典案例:二分查找¶
下面来看看最后一个递归示例——二分查找算法。
你可能熟悉猜心游戏。这个游戏要求猜对对方心里想的是什么,且整个猜测过程提出的“是 否”问题不能超过20个。为充分利用每个问题,你力图让每个问题的答案将可能的范围减半。例 如,如果你知道对方心里想的是一个人,可能问:“你心里想的是个女人吗?”除非你有很强的 第六感,不然不会一开始就问:“你心里想的是John Cleese吗?”对喜欢数字的人来说,这个游戏的另一个版本是猜数。例如,对方心里想着一个1~100的数字,你必须猜出是哪个。当然,猜100次肯定猜对,但最少需要猜多少次呢?
实际上只需猜7次。首先问:“这个数字大于50吗?”如果答案是肯定的,再问:“这个数字 大于75吗?”不断将可能的区间减半,直到猜对为止。你无需过多地思考就能成功。 这种策略适用于众多其他不同的情形。一个常见的问题是:指定的数字是否包含在已排序的 序列中?如果包含,在什么位置?为解决这个问题,可采取同样的策略:“这个数字是否在序列 中央的右边?”如果答案是否定的,再问:“它是否在序列的第二个四分之一区间内(左半部分 的右边)?”依此类推。明确数字所处区间的上限和下限,并且每一个问题都将区间分成两半。
这里的关键是,这种算法自然而然地引出了递归式定义和实现。先来回顾一下定义,确保你 知道该如何做。
如果上限和下限相同,就说明它们都指向数字所在的位置,因此将这个数字返回。
否则,找出区间的中间位置(上限和下限的平均值),再确定数字在左半部分还是右半部 分。然后在继续在数字所在的那部分中查找。
在这个递归案例中,关键在于元素是经过排序的。找出中间的元素后,只需将其与要查找的 数字进行比较即可。如果要查找的数字更大,肯定在右边;如果更小,它必然在左边。递归部分 为“继续在数字所在的那部分中查找”,因为查找方式与定义所指定的完全相同。(请注意,这种 查找算法返回数字应该在的位置。如果这个数字不在序列中,那么这个位置上的自然是另一个数 字。)
现在可以实现二分查找了。
>>> def search(sequence, number, lower, upper):
>>> if lower == upper:
>>> assert number == sequence[upper]
>>> return upper
>>>
>>> else:
>>> middle = (lower + upper) // 2
>>> if number > sequence[middle]:
>>> return search(sequence, number, middle + 1, upper)
>>> else:
>>> return search(sequence, number, lower, middle)
这些代码所做的与定义完全一致:如果lower == upper,就返回upper,即上限。请注意,你假设(断言)找到的确实是要找的数字(number == sequence[upper])。如果还未达到基线条件, 就找出中间位置,确定数字在它左边还是右边,再使用新的上限和下限递归地调用search。为方 便调用,还可将上限和下限设置为可选的。为此,只需给参数lower和upper指定默认值,并在函数开头添加如下条件语句:
>>> def search(sequence, number, lower=0, upper=None):
>>> if upper is None:
>>> upper = len(sequence) - 1
现在,如果你没有提供上限和下限,它们将分别设置为序列的第一个位置和最后一个位置。 下面来看看这是否可行。
>>> seq = [34, 67, 8, 123, 4, 100, 95]
>>> seq.sort()
>>> seq
[4, 8, 34, 67, 95, 100, 123]
>>> def search(sequence, number, lower=0, upper=None):
>>> if upper is None:
>>> upper = len(sequence) - 1
>>> search(seq, 34)
2
>>> search(seq, 100)
5
然而,为何要如此麻烦呢?首先,你可使用列表方法index来查找。其次,即便你要自己实 现这种功能,也可创建一个循环,让它从序列开头开始迭代,直至找到指定的数字。
确实,使用index挺好,但使用简单循环可能效率低下。前面说过,要在100个数字中找到指 定的数字,只需问7次;但使用循环时,在最糟的情况下需要问100次。你可能觉得“没什么大不 了的”。但如果列表包含100 000 000 000 000 000 000 000 000 000 000 000个元素(对Python列表来 说,这样的长度可能不现实),使用循环也将需要问这么多次,情况开始变得“很大”了。然而, 如果使用二分查找,只需问117次。
8.6.3. 函数式编程¶
Python提供了一些有助于进行这种函数式编程的函数: map
、filter
和 reduce
。 在较新的 Python版本中,函数 map
和 filter
的用途并不大,应该使用列表推导来替代它们。 你可使用 map
将序列的所有元素传递给函数。
>>> list(map(str, range(10)))
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
上面的语句与下面的列表推导式等价:
>>> [str(i) for i in range(10)]
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
你可使用 filter
根据布尔函数的返回值来对元素进行过滤。
>>> def func(x):
>>> return x.isalnum()
>>>
>>> seq = ["foo", "x41", "?!", "***"]
>>> list(filter(func, seq))
['foo', 'x41']
就这个示例而言,如果转而使用列表推导,就无需创建前述自定义函数。
>>> [x for x in seq if x.isalnum()]
['foo', 'x41']
实际上,Python提供了一种名为lambda表达式的功能,让你能够创建内嵌的简单函数(主要供map、filter和reduce使用)。
>>> filter(lambda x: x.isalnum(), seq)
<filter at 0x7fb9306bb6d8>
然而,使用列表推导的可读性不是更高吗?
下面再来说第3个函数 reduce
。
要使用列表推导来替换函数 reduce
并不那么容易,而这个函数提供的功能即便能用到,也用得不多。
它使用指定的函数将序列的前两个元素合二为一,再将结果与第3个元素合二为
一,依此类推,直到处理完整个序列并得到一个结果。
例如,如果你要将序列中的所有数相加,可结合使用 reduce
和
lambda x, y: x+y
。
>>> numbers = [72, 101, 108, 108, 111, 44, 32, 119, 111, 114, 108, 100, 33]
>>> from functools import reduce
>>> reduce(lambda x, y: x + y, numbers)
1161
8.6.4. 小结¶
本章介绍了抽象的基本知识以及函数。
抽象:抽象是隐藏不必要细节的艺术。通过定义处理细节的函数,可让程序更抽象。
函数定义:函数是使用def语句定义的。函数由语句块组成,它们从外部接受值(参数), 并可能返回一个或多个值(计算结果)。
参数:函数通过参数(调用函数时被设置的变量)接收所需的信息。在Python中,参数有 两类:位置参数和关键字参数。通过给参数指定默认值,可使其变成可选的。
作用域:变量存储在作用域(也叫命名空间)中。在Python中,作用域分两大类:全局作 用域和局部作用域。作用域可以嵌套。
递归:函数可调用自身,这称为递归。可使用递归完成的任何任务都可使用循环来完成, 但有时使用递归函数的可读性更高。
函数式编程:Python提供了一些函数式编程工具,其中包括lambda表达式以及函数map、filter和reduce。