7.5 递归
在7.1.2节编写斐波那契数列函数的时候，使用了 Python 中的递归（Recursion）。固然 Python 创始人对递归有个人的看法，此处还是要用单独一节专门给予介绍。等读者阅读完本节内容，也能理解之所以如此重视递归的原因了。
7.5.1 了解递归
递归的英文单词 “recursion” 来自拉丁语中的 recurre，意思是：匆匆而归、返回、还原或重现。各类资料中对递归的定义虽有所不同，但综合来看，都有“在被定义的对象中使用定义本身”的含义，例如：
代码语言：javascript复制>>> 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 ，逐渐接近终止条件。
注意，上面的写法纯粹是为了突出递归和终止条件，还可以有一种更简洁的表达方式：
代码语言：javascript复制>>> 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 循环实现。
代码语言：javascript复制>>> def count_down(n):
... while n >= 0:
... print(n)
... n -= 1
...
>>> count_down(5)
5
4
3
2
1
0
比较两种不同的实现方式，从可读性角度来看，都一样清晰直观。
7.5.2 阶乘
阶乘是所有介绍递归的资料中都必须要选择的案例，本书也不免俗。其数学定义如下：
如果用适合于应用递归的方式表示，则为：
与上面的示例一样，基本事件是不需要递归就可以实现的；更复杂的事件则可简化，也就是将其简化为基本事件之一:
其中：
- n = 0 或 n = 1 时是终止条件，此时不需要递归就可以得到阶乘的结果。
- 如果 nge2 ，要调用 (n - 1)! ，通过递归逐步接近终止条件。
例如计算 4! ，用递归算法，其过程如图7-5-1所示。依次计算 4! 、3! 和 2! ，直到 n = 1 时的终止条件，无需进一步递归就可以计算 1! 。
图7-5-1 4! 递归计算过程
根据上述分析，编写如下实现函数：
代码语言：javascript复制>>> 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 循环编写的阶乘函数。
代码语言：javascript复制>>> 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.8553times 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万次，得到上述结果（不同计算机会有差异）。
再用同样的形式，测试另外两个实现阶乘的函数。
代码语言：javascript复制# 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 实现的相应函数运行速度更快。
7.5.3 快速排序算法
算法，对于编程而言，其重要性不言而喻，只是不在本书的范畴之内。由于本节旨在介绍递归，用递归理解快速排序算法又是一件顺手牵羊的事情，故安排本小节。
快速排序（Quicksort）是英国计算机科学家 Tony Hoare 于1959年提出的。下面通过一个示例理解这个算法的基本步骤。假设有列表 lst = [1, 3, 9, 7, 2, 5, 4, 8] ，根据快速排序算法：
- 从列表中选出一项，称之为基准（Pivot）。基准可以是列表中的任何一项，理论上可以任意选择，但实践中有一定的规则——留待后话。此处先从
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 = []
在快速排序中，基准往往“只有更好，没有最好”，但也不意味着可以随意选。如果待排序的数据是是随机分布的，以第一项与最后一项为基准是常见的选择；如果数据已经或者几乎已经有一定的顺序，通常会选择中间项作为基准。如果无法提前预知，则可以用一种较为常用的方法：找到数据序列中第一项、最后一项和中间项，计算这三项的中位数，并以其作为基准（参考下面的程序）。
理解了快速排序基本原理之后，就可以编写实现程序了。
代码语言：javascript复制#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() 就是按照前述快速排序算法编写，有关解释如下：
- 注释（3）判断实参的序列长度，如果为空或者只有一个元组，则到达了递归的终止条件，返回该序列。
- 注释（4）的逻辑行，通过计算序列的第一个项、中间项、最后一项三个成员的中值，确定基准的值。
- 注释（5）的逻辑行，根据基准对序列分区。
- 注释（6）的逻辑行，对分区所得到的序列进行递归，然后组合成排好序的序列
注意，以上只是为了与前述快速排序算法保持一致而编写的代码，其本身还有继续优化的空间，比如注释（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)
执行程序，查看输出结果。
代码语言：javascript复制% python quicksort.py
[-18, 31, 23, -14, -31, 25, -28, 16, -13, -41]
[-41, -31, -28, -18, -14, -13, 16, 23, 25, 31]
用简短的语言概括递归：对自身的调用。
最后要强调，递归并非对所有的任务都适用。如果递归能够让程序的可读性非常好，这时应该毫不犹豫地使用——递归没有死。如果与循环等相比较，递归并没有显示出很高的可读性，那么就要谨慎从事了，它毕竟牺牲了执行速度并占用了更多内存。
