了解递归

★本文是《Python 完全自学教程》书稿节选，先睹为快。 ”

7.5 递归

在7.1.2节编写斐波那契数列函数的时候，使用了 Python 中的递归（recursion）。固然 Python 创始人对递归有个人的看法，此处还是要用单独一节专门给予介绍。等读者阅读完本节内容，也能理解之所以如此重视递归的原因了。

7.5.1 了解递归

递归（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

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

点击 【阅读原文】 查看更多关于本书的信息。