在7.1.2节编写斐波那契数列函数的时候,使用了 Python 中的递归(Recursion)。固然 Python 创始人对递归有个人的看法,此处还是要用单独一节专门给予介绍。等读者阅读完本节内容,也能理解之所以如此重视递归的原因了。
递归的英文单词 “recursion” 来自拉丁语中的 recurre,意思是:匆匆而归、返回、还原或重现。各类资料中对递归的定义虽有所不同,但综合来看,都有“在被定义的对象中使用定义本身”的含义,例如:
>>> def func():
... x = 7
... func()
...
在所定义的函数 func()
内调用 func()
自身,这就是递归的表现形式。运用7.3.3节有关变量作用域的知识来理解函数 func()
的执行过程,第一次执行的时候,会创建 x = 7
;然后调用 func()
自身,这是第二次运行,再次创建 x = 7
,但是与前面的 x
处于不同的作用域,所以二者不会发生冲突。
不幸的是,如果真的执行执行上面的所定义的 func()
函数,会得到不太好的结果,如下所示:
>>> func()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 3, in func
File "<stdin>", line 3, in func
File "<stdin>", line 3, in func
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
理论上将,func()
函数会永远执行,一遍又一遍地调用自己,而没有任何返回值。在实践中,绝对不允许出现这样的递归。Python 解释器会自动限制递归的深度,当达到该极限值时,会引发 RecursionError
异常,如上所示。如果想了解当前 Python 解释器的限制是多少,可以使用 sys 模块中的 getrecursionlimit()
函数。
>>> from sys import getrecursionlimit
>>> getrecursionlimit()
1000
以上所得到的返回值 1000
是 Python 解释器默认的对的递归次数的限制值,即最多能够重复调用 func()
函数自身的次数。也可以用此模块中的 setrecursionlimit()
函数修改此值。
>>> from sys import setrecursionlimit
>>> setrecursionlimit(200)
>>> getrecursionlimit()
200
>>> func()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 3, in func
File "<stdin>", line 3, in func
File "<stdin>", line 3, in func
[Previous line repeated 196 more times]
RecursionError: maximum recursion depth exceeded
从返回的异常信息中,可以看到修改后的效果。
在真正的递归算法中,如同7.1.2节的斐波那契数列函数那样,必须有一个终止条件,即不需要进一步递归,就可以直接得到结果。在不满足终止条件时,每次递归都是逐渐接近此终止条件。例如编写一个“倒数计数”的函数——所谓“倒计时”,如: 5, 4, 3, 2, 1, 0
。
>>> def count_down(n):
... print(n)
... if n == 0: return # (1)
... else:
... count_down(n-1) # (2)
...
>>> count_down(5)
5
4
3
2
1
0
其中,注释(1)就是终止条件,当 n
为 0
时停止递归;否则,如注释(2),调用所定义的函数,其参数为 n-1
,逐渐接近终止条件。
注意,上面的写法纯粹是为了突出递归和终止条件,还可以有一种更简洁的表达方式:
>>> def count_down(n):
... print(n)
... if n > 0: count_down(n-1)
...
>>> count_down(5)
5
4
3
2
1
0
当然,因为以上函数中没有对 n
做任何检查和限制,如果执行 count_down(-5)
,则不会执行“倒计时”。读者如果有兴趣,可以继续对上述函数进行优化。
其实,在大多数情况下,编程中可以不用递归,即递归通常是不必须的——所以会有“递归已死”的观点。比如上面的“倒计时”,也可以用 while 循环实现。
>>> def count_down(n):
... while n >= 0:
... print(n)
... n -= 1
...
>>> count_down(5)
5
4
3
2
1
0
比较两种不同的实现方式,从可读性角度来看,都一样清晰直观。
阶乘是所有介绍递归的资料中都必须要选择的案例,本书也不免俗。其数学定义如下:
如果用适合于应用递归的方式表示,则为:
与上面的示例一样,基本事件是不需要递归就可以实现的;更复杂的事件则可简化,也就是将其简化为基本事件之一:
其中:
例如计算 4! ,用递归算法,其过程如图7-5-1所示。依次计算 4! 、3! 和 2! ,直到 n = 1 时的终止条件,无需进一步递归就可以计算 1! 。
图7-5-1 4! 递归计算过程
根据上述分析,编写如下实现函数:
>>> def factorial(n):
... return 1 if n <= 1 else n * factorial(n-1)
...
>>> factorial(4)
24
在 factorial()
函数中使用了第6章6.2节的“三元操作”,将条件语句写成了一行。要想看到函数内部的执行过程,可以增加 print()
函数,将参数 n
以及返回值打印出来。
>>> def factorial(n):
... print(f"factorial() called with n = {n}")
... value = 1 if n <= 1 else n * factorial(n-1)
... print(f"--> factorial({n}) returns {value}")
... return value
...
>>> factorial(4)
factorial() called with n = 4
factorial() called with n = 3
factorial() called with n = 2
factorial() called with n = 1
--> factorial(1) returns 1
--> factorial(2) returns 2
--> factorial(3) returns 6
--> factorial(4) returns 24
24
将上述输出结果与图7-5-1进行对比,从而理解此函数中的递归过程。
同样,不用递归,也能实现阶乘,下面的示例就是用 for 循环编写的阶乘函数。
>>> def factorial_for(n):
... value = 1
... for i in range(2, n+1):
... value *= i
... return value
...
>>> factorial_for(4)
24
除此之外,还可以用一个名为 reduce()
的函数实现阶乘——注意,reduce()
在当前版本的 Python 中已经不是内置函数,它在模块 functools
内。
>>> from functools import reduce
>>> reduce(lambda x, y: x+y, [1, 2, 3, 4, 5])
15
在上述示例中,使用 reduce()
函数,将列表 [1, 2, 3, 4, 5]
中的各项从做向右,依次累加相加,即实现计算 ((((1+2)+3)+4)+5)
的结果。将之用于阶乘函数:
>>> def factorial_reduce(n):
... return reduce(lambda x, y: x*y, range(1, n+1) or [1])
...
>>> factorial_reduce(4)
24
这表明一个问题通常有多个解决方案——现实世界没有标准答案,如何选择?要具体问题具体分析。假如比较看重函数的执行速度,可以使用7.3.4节中创建的文件 timing.py
中的装饰器 timing_func()
测量以上三种实现阶乘的函数的性能——这仅仅是一种方法。测量程序执行速度也有多种方法,下面就介绍另外一种:使用 timeit
模块中的 timeit()
的函数,这个函数支持多种不同的调用形式,此处将用下面的方式调用:
timeit(<command>, setup=<setup_string>, number=<iterations>)
执行 timeit()
函数时,首先调用 setup
参数的值 <setup_string>
中指令,然后按照 number
参数的值执行 <command>
操作 <iterations>
次,并报告累计的执行时间(以秒为单位)。
>>> timeit('print(s)', setup="s='python'", number=3)
python
python
python
2.855300044757314e-05
不同的本地计算机,所显示的执行时间会有所差异。上述代码中,setup
参数实现了对变量 s
赋值为字符串 'python'
的操作。然后将 print(string)
指令执行 number=3
次。最终显示执行时间是 2.855300044757314e-05
s (大于 2.8553\times 10^{-5} s )。
下面使用 timeit()
来比较实现阶乘的三种方式的性能。
>>> setup_string = """
... print("recursive:")
... def factorial(n):
... return 1 if n <= 1 else n * factorial(n-1)
... """
>>> timeit("factorial(4)", setup=setup_string, number=10000000)
recursive:
5.70697866699993
变量 setup_string
是字符串,其中定义了相关的 factorial()
函数。然后,timeit()
执行 factorial(4)
总共1000万次,得到上述结果(不同计算机会有差异)。
再用同样的形式,测试另外两个实现阶乘的函数。
# for 循环
>>> setup_string = """
... print('for loop:')
... def factorial(n):
... value = 1
... for i in range(2, n+1):
... value *= 1
... return value
... """
>>> timeit("factorial(4)", setup=setup_string, number=10000000)
for loop:
4.367680199000461
# reduce() 函数
>>> setup_string = """
... from functools import reduce
... print("reduce():")
... def factorial(n):
... return reduce(lambda x, y: x*y, range(1, n+1) or [1])
... """
>>> timeit("factorial(4)", setup=setup_string, number=10000000)
reduce():
8.28644317600265
从上述测试可知,用 for 循环的最快,递归解决方案也不算太慢,倒是 reduce()
的实现是最慢的。当然,必须要注意,上述测试是在执行了1000万次 factorial(4)
才显现出来的。是否以此为编程实际中的取舍依据,是值得讨论的。毕竟在编程实践中,“可读性”的原则要优先于“执行速度”(也有的开发者不认同此观点)。
总而言之,递归可能会导致代码执行时间变长。
其实,真正的 Python 开发中,根本不需要我们编写一个实现阶乘的函数,因为标准库的 math
模块中已经提供了。
>>> from math import factorial
>>> factorial(4)
24
>>> setup_string = "from math import factorial"
>>> timeit("factorial(4)", setup=setup_string, number=10000000)
0.4651583060003759
是不是很惊讶,math.factorial()
的运行时间大约是 for 循环的十分之一,因为用 C 语言实现的函数几乎总是比用纯 Python 实现的相应函数运行速度更快。
算法,对于编程而言,其重要性不言而喻,只是不在本书的范畴之内。由于本节旨在介绍递归,用递归理解快速排序算法又是一件顺手牵羊的事情,故安排本小节。
快速排序(Quicksort)是英国计算机科学家 Tony Hoare 于1959年提出的。下面通过一个示例理解这个算法的基本步骤。假设有列表 lst = [1, 3, 9, 7, 2, 5, 4, 8]
,根据快速排序算法:
lst
列表中任选一项,假设是 lst[5]
所对应的成员 5
。5
,可以将列表 lst
分为三个子列表,一个子列表中的成员都小于 5
,另一个子列表的成员都大于 5
,将这称为分区(Partition)。还有一个由基准 5
组成的列表。lst_31 = [7]
lst_32 = [8]
lst_33 = [9]
lst_11 = [1, 2]
继续使用前述方法,从 lst_11
中选定基准(假设是 1
),并生成如下列表:lst_12 = [3]
lst_13 = [4]
lst_111 = []
lst_112 = [1]
lst_113 = [2]
lst_1 = [1, 3, 2, 4]
继续使用前述方法,从 lst_1
中选定基准(假设是 3
),并生成如下列表:lst_2 = [5]
lst_3 = [9, 7, 8]
继续使用前述方法,从 lst_3
中选定基准(假设是 8
),并生成如下列表:当最终得到的子列表中为空或只有一个成员时,就达到了递归的终止条件。然后将所有达到终止条件的非空子列表链接起来,即得到了对 lst
的排序结果:lst_112 + lst_113 + lst_12 + lst_13 + lst_2 + lst_31 + lst_32 + lst_33 = [1, 2, 3, 4, 5, 7, 8, 9]
。
由上述演示过程可知:
lst_3
,如果用 9
做基准,在得到了子列表之后,还要再次迭代,才能最终达到终止条件。
lst_3 = [9, 7, 8]
,以 9
为基准,生成子列表:lst_311 = []
lst_312 = [7]
lst_313 = [8]
lst_31 = [7, 8]
以 7
为基准,生成子列表:lst_32 = [9]
lst_33 = []
在快速排序中,基准往往“只有更好,没有最好”,但也不意味着可以随意选。如果待排序的数据是是随机分布的,以第一项与最后一项为基准是常见的选择;如果数据已经或者几乎已经有一定的顺序,通常会选择中间项作为基准。如果无法提前预知,则可以用一种较为常用的方法:找到数据序列中第一项、最后一项和中间项,计算这三项的中位数,并以其作为基准(参考下面的程序)。
理解了快速排序基本原理之后,就可以编写实现程序了。
#coding:utf-8
'''
filename: quicksort.py
'''
import statistics
def quick_sort(numbers):
if len(numbers) <= 1: # (3)
return numbers
else:
pivot = statistics.median([
numbers[0],
numbers[len(numbers)//2],
numbers[-1]]) # (4)
items_less, pivot_items, items_greater = (
[n for n in numbers if n < pivot],
[n for n in numbers if n == pivot],
[n for n in numbers if n > pivot]) # (5)
return (
quick_sort(items_less) + \
pivot_items + \
quick_sort(items_greater)) # (6)
上述程序中定义的函数 quick_sort()
就是按照前述快速排序算法编写,有关解释如下:
注意,以上只是为了与前述快速排序算法保持一致而编写的代码,其本身还有继续优化的空间,比如注释(5)的逻辑行就不是最佳方案——有兴趣的读者可以深入研究。总之,从 quick_sort()
函数中已经看到递归的身影了。
为了便于测试,可以定义一个简短的函数来生成一个由 1
到 100
的随机数字列表(继续在 quicksort.py
文件中写入下述代码)。
import random
def get_random_numbers(length, minimum=1, maximum=100):
return [random.randint(minimum, maximum) for _ in range(length)]
if __name__=='__main__':
nums = get_random_numbers(10, -50, 50)
print(nums)
nums_sorted = quick_sort(nums)
print(nums_sorted)
执行程序,查看输出结果。
% python quicksort.py
[-18, 31, 23, -14, -31, 25, -28, 16, -13, -41]
[-41, -31, -28, -18, -14, -13, 16, 23, 25, 31]
用简短的语言概括递归:对自身的调用。
最后要强调,递归并非对所有的任务都适用。如果递归能够让程序的可读性非常好,这时应该毫不犹豫地使用——递归没有死。如果与循环等相比较,递归并没有显示出很高的可读性,那么就要谨慎从事了,它毕竟牺牲了执行速度并占用了更多内存。