递归

编写斐波那契数列函数的时候，使用了 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

比较两种不同的实现方式，从可读性角度来看，都一样清晰直观。

根据上述分析，编写如下实现函数：

>>> 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 （大于 ）。

下面使用 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] ，根据快速排序算法：

1. 从列表中选出一项，称之为基准（Pivot）。基准可以是列表中的任何一项，理论上可以任意选择，但实践中有一定的规则——留待后话。此处先从 lst 列表中任选一项，假设是 lst[5] 所对应的成员 5 。
2. 根据基准 5 ，可以将列表 lst 分为三个子列表，一个子列表中的成员都小于 5 ，另一个子列表的成员都大于 5 ，将这称为分区（Partition）。还有一个由基准 5 组成的列表。
   1. lst_31 = [7]
   2. lst_32 = [8]
   3. lst_33 = [9]
   4. lst_11 = [1, 2]继续使用前述方法，从 lst_11 中选定基准（假设是 1 ），并生成如下列表：
   5. lst_12 = [3]
   6. lst_13 = [4]
   7. lst_111 = []
   8. lst_112 = [1]
   9. lst_113 = [2]
   10. lst_1 = [1, 3, 2, 4]继续使用前述方法，从 lst_1 中选定基准（假设是 3），并生成如下列表：
   11. lst_2 = [5]
   12. 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() 就是按照前述快速排序算法编写，有关解释如下：

• 注释（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)

执行程序，查看输出结果。

% python quicksort.py
[-18, 31, 23, -14, -31, 25, -28, 16, -13, -41]
[-41, -31, -28, -18, -14, -13, 16, 23, 25, 31]

用简短的语言概括递归：对自身的调用。

最后要强调，递归并非对所有的任务都适用。如果递归能够让程序的可读性非常好，这时应该毫不犹豫地使用——递归没有死。如果与循环等相比较，递归并没有显示出很高的可读性，那么就要谨慎从事了，它毕竟牺牲了执行速度并占用了更多内存。