1.2.4 递归函数

在函数的内部还可以调用函数，不过一般来说再次调用的函数都是其他函数，如果再次调用的函数是函数本身，那么这个函数就是递归函数。一个十分经典的例子就是阶乘的计算（为了简化，未考虑0的阶乘）。阶乘的概念很简单：n! = nx(n-1)x(n-2)x...2x1。基于此，可以写出计算阶乘的函数，如下所示。

    def factorial_normal(n):
        result = 1
        for i in range(n):
          result = result * n
          n = n -1
        return result

这是一种解决的方法，逻辑比较简单，下面来看递归的实现方式。根据阶乘的概念，可以得到n! =nx(n-1)!。基于此，我们可以写出如下计算阶乘的递归函数。

    def factorial_recursion(n):
        if n == 1:
          return 1
        return n * factorial_recursion(n -1)

假设执行factorial_recursion(5)，其逻辑如下。

    factorial_recursion(5)
    = 5 * factorial_recursion(4)
    = 5 * 4 * factorial_recursion(3)
    = 5 * 4 * 3 * factorial_recursion(2)
    = 5 * 4 * 3 * 2 * factorial_recursion(1)
    = 5 * 4 * 3 * 2 * 1
    = 120

这两种方法都是可行的，但是很明显使用递归的方式要更加简捷一些，而且可以清晰地看出计算的逻辑。在后面爬虫断线重连机制的实现上就使用了递归函数，它使得爬虫程序更加稳健。除此之外，递归在图的遍历、数据结构的构造等方面都有十分广泛的应用。当然，递归也有其缺点，在调用次数过多时会造成栈溢出。例如这里计算factorial_recursion(1000)就会报错：RecursionError: maximum recursion depth exceeded in comparison。