第十三章：递归

说到递归，或许你也听说过递推，这两个概念其实应该算到算法的行列，在python编程入门的教程中我们也只是简单的讲一下，知道这个概念以及可以简单的应用就可以；本章其实也应该属于函数的范畴，因为只要用到递归，就肯定需要借助函数，所以本章也作为函数的一个延伸和应用来讲。

13.1 递归、递推傻傻分不清楚

首先我们通过一个数学问题来深入区分一下递推和递归，阶乘这个概念想必每个人在初高中就已经开始接触了，如果我们说5的阶乘，那结果则是1 x 2 x 3 x 4 x 5所得到的积；以此类推，一个n的阶乘则是从1 x 2 x 3 x … x n，让我们算阶乘的方式，在上学时可能只有手算或者是使用计算器来逐一做乘法运算，但现在我们使用编程语言却可以只用几行代码来实现所有数字阶乘的运算，接下来我们分别使用递推和递归来编写求阶乘的程序。

13.1.1 使用递推进行的阶乘运算

首先我们通过概念来了解一下什么是递推：

递推是按照一定的规律来计算序列中的每个项，通常是通过计算前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。

接下来我们直接编写并分析下面通过递推来实现求阶乘算法的代码：

def factorial(n):
    number = 1
    for i in range(1, n + 1):
        number = number * i
    return number

print(factorial(5))

结果：

120

上面的代码是通过递推的方式来实现对5做的阶乘，可以发现这块代码的逻辑很简单，我们首先定义一个初始值为1的number变量（初始化为1的原因是1乘以任何数都为这个数，不会对结果有影响），然后我们使用for循环，同样需要确定for循环中i要从1开始赋值（不从0开始是因为0乘以任何数都为0），然后for循环的最后一个数字应该是n，所以这里需要写入n + 1（for循环的用法是包含开始的数，不包含结束的数字，也就是前闭后开），这样就可以实现从1 x 2 到 x n的功能；让我们感觉用起来比较简单的原因就是递推的过程就像是一条向一个方向延伸的直线，规律明了，路径清晰；但接下来要说的递归就没这么简单了。

13.1.2 使用递归进行的阶乘运算

接下来我们还是先看一下递归的说法：

递归，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。

比如像下图一样的情景我们肯定见到过：

另外，我们在看一些主播打开直播软件的时候也会看到这样一层层重复画面的情景；甚至我还记得在某个星级饭店上厕所时，整个厕所的四面都是全尺寸的玻璃，映射出无数个我陪我一起上厕所，真的是贴心。

这些类似的情景可以作为递归的可视化概念来进行理解，当然我们还是通过求阶乘的方式来分析代码，从而对递归有一个更好的认识：

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))

结果：

120

通过使用递归的方式，同样可以得到正确的答案，并且看似代码更加简洁，我们来分析一下上述代码：当我们向factorial函数内传入数字5之后，首先会通过if语句来进行判断，如果满足n == 1，则直接返回数字1；否则，会返回n * factorial(n - 1)；这种方式在你第一眼看来肯定会有些奇怪，但这就是递归的普遍特性，就像上文对递归的解释：递归通常表现为函数调用函数本身的一种方法；所以factorial(n - 1)又会继续展开，此时会向factorial函数传入数字4，同样不满足n == 1，所以还会进一步返回factorial(n - 1)，直到 n == 1，返回数字1为止，我们可以通过下图来理解当前的递归流程：

这个过程并不像是递推一样，只有一条直线延伸的逻辑，而是到直线“尽头”又一层一层返回结果的一个过程；所以递归相对于递推来说，就仿佛是多拐了一个弯儿，虽然可以实现同样的功能，并且难度还比递推要大，但之后有些场合下，递归才是天才程序员的首选；所以递归，是变成天才程序员的第一步。

13.2 兔子，兔子，又是兔子

讲到递归，我们必不可少的会讲到另一个关于兔子的数学案例–斐波那契数列；问题描述是这样的：如果一对兔子在出生两个月后就有繁殖能力，之后的每个月都能生出一对小兔子，假设生出的每对兔子都是雌雄各一只，并且所有兔子都不会死去，那么一年之后这一家族会有多少对兔子。

我们首先通过下面一张图片来进行可视化的观察：

首先第A对兔子在前两个月是没有繁殖能力的，所以均是一对兔子；然后在第三个月，由第A对兔子繁殖出第B对兔子；到第四个月，第B对兔子依旧没有繁殖能力，由第A对兔子又繁殖出第C对兔子，所以在第四个月，有三对兔子共存；所以数据统计如下图所示：

我们通过对上图表格数据的分析，可以发现一个很明显的规律：从3月份开始，每月的兔子总对数都是前两个月的和，因此可以得到以下分段函数：

13.2.1 递推方式的斐波那契数列

同样，递归能完成的功能，使用递推会更好理解一些；我们先通过递推的方式来编写一个斐波那契数列的函数：

def Fib(n):
    f1 = 1
    f2 = 1
    if (n <= 2):
        return 1
    else:
        for i in range(n - 2):
            f3 = f1 + f2
            f1 = f2
            f2 = f3
        return f3

print(Fib(10))

然后我们分析上述代码，我们定义了一个用于求斐波那契数列的一个递推函数，首先定义f1和f2的初始值都是1，并且使用if判断当输入的n小于或等于2时，都得到结果1，所以直接return 1；在n大于2时则满足Fib(n) = Fib(n -1 ) + Fib(n - 2)的表达式，所以借助for循环进行递推，另外for的循环次数受到n的影响，需要使用n减去已经初始化为1的前两个数据的循环次数，接下来for循环内的语句就像是推箱子一样，f3为f1和f2的和，然后f1和f2分别向前推进一位，通过递推就可以得到相应的斐波那契数列。

13.2.2 递归方式的斐波那契数列

递推的方式清晰易懂，但递归才是我们的最终选择，接下来我们先看一下使用递归求斐波那契数列的原理图：

通过原理图可以发现整个递归流程是先顺向拆解，然后逆向返回求和，确实在思路上是要比递推要复杂一些的，然后我们根据原理图编写递归求斐波那契数列的程序：

def Fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        return Fib(n - 1) + Fib(n - 2)

print(Fib(10))

通过对比递推和递归的代码，我们可以发现很明显的一个规律；递推的实现原理很简单，但我们需要付出更多代码量，递归的原理相比较复杂，但我们却可以使用较少的代码来完成，就好像把一个比较重的任务直接丢给递归来做：“自己调用自己去吧，我就不管了”。

除了我们所说的递归逻辑复杂，但代码较少并清晰的特点之外，我们还有必要说一下递归的缺点，多数情况下，递归的效率是要比递推要低很多的，从两者的运行原理就可以看出来，递归需要不断的调用自身，确实会比递推要执行更多的语句，我们知道每执行一行语句都是消耗时间的，代码少的话几乎感受不到，但如果我们使用递归来算100个月之后的兔子数量，两者的运行时间就会有明显的差别了。所以听我一句劝，并不是使用递归就可以称神了，而是需要在适合的情况下来利用好这个神奇的算法，当然这需要大量的项目经验，当前只有能理解并简单使用递归算法就足够了。

最后再总结一下递归需要满足的三个条件：

1.必须有一个明确的结束条件；
2.每次进入更深一层递归时，问题规模相比上次递归都应有所减少
3.相邻两次重复之间有紧密的联系，前一次要为后一次做准备