AI_第一部分 数据结构与算法（9.递归）

第四阶段我们进行深度学习(AI)，本部分（第一部分）主要是对底层的数据结构与算法部分进行详尽的讲解，通过本部分的学习主要达到以下两方面的效果：

1.对开发中常见的算法能应用自如，让你在跳槽找工作中“算法题”不再是阻碍你“钱途”的拦路虎。

2.我们不需要调参数的调参攻城狮，我们要做正真的自己的AI模型。

3.本部分预计40篇左右。

今天我们聊聊递归，递归实现起来是很简单的，但是什么时候能想到去用递归？怎么去构建一个递归呢？你是怎么思考的呢？

1.如何理解递归？

递归是一种使用非常广泛的算法。从字面意思来解释一下：把要求解的问题进行分解的过程就是“递”，分解之后“合”起来的过程就是“归”。基本上，所有的递归问题都可以用地推公式来表示。

2.构成递归的三个条件

2.1.一个问题的解决可以分解为几个子问题的解

何为子问题？“子”就是数据规模比之前更小的问题。

2.2.求解的这个问题与分解之后的子问题，除了数据规模不同，求解的思路是完全相同的。

2.3.存在递归终止条件

把问题分解为子问题，子问题再分解为子子问题，一层层分解下去，这就会存在无限循环，这就需要有终止条件。

3.如何编写递归代码？

其一就是写出递归公式，其二就是找到终止条件。剩下的就是将递推公式转化为代码就ok.

4.举例

假设有n个台阶，每次你呢可以跨越1个或者2个，请问走这个台阶你有多少种走法呢？

我们可以思考一下，根据第一步的走法可以把所有的走法分为两类，第一类是第一步走了1个台阶，另外一类是第一步走了2个台阶。所以n个台阶的走法是等于先走1个台阶后，n-1个台阶的走法加上先走2个台阶后，n-2个台阶的走法。我们可以简单的使用数学公式表示为：f(n) = f(n-1) + f(n-2). 有了递推公式后我们再看一下终止条件。当有1个台阶的时候，我们不需要再继续递归，就只有1种走法。所以f(1) = 1.我们可以使用小样本数据进行一次验证。当n=2时候，f（2） = f（1） + f(0) 如果递推终止条件只有f(1) = 1,那f(2)就无法求解了。所以除了f(1) = 1这个终止条件外还应该有f(0) = 1,这表示走0个台阶有一种走法，这种不太符合正常的逻辑思维，所以我们可以用f(2) = 2 作为一种终止条件，表示走2个台阶有2种走法，一步走完或者分两步走完。

我们把递推终止条件和递推公式放在一起可以得到：

f(1) = 1

f（2） = 2

f(n) = f(n-1) + f(n-2)

有了递推公式我们转化成为最终代码：

def f(n): """

求解递推问题

"""

if n == 1: return 1

if n == 2: return 2

return f(n-1) + f(n-2)

总结一下：

写递归代码关键就是找到如何袶大问题分解为小问题的规律，并且基于此写出地推公式，然后再敲定终止条件，最后通过终止条件和地推公式转化成代码。在编写递归代码的过程中，不用想每一层的调用关系，不要试图用人脑分解递归的每一步骤。

5.递归代码防止堆栈溢出问题

函数调用会使用栈来保存临时的变量。每调用一个函数，都会将临时变量分装称为栈帧压入内存栈中，等函数执行完成返回时，才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归的深度很深一直压栈，就会有堆栈溢出的风险。

如何解决呢？可以在代码中限制递归调用的最大深度方式来解决这个问题，不过还是不能从根本上解决这个问题。

6.递归代码警惕重复计算

我们还是用上面台阶的例子，f(5) 会计算f(4) 和f(3),f(4)会计算f(3) 和f(2)这样f(3)多次被计算。为了避免多次重复计算，我们可以使用一个数据结构（散列表）来保存已经求解过的f（k）,当递归调用到f(k),如果之前有就直接使用，没有才去计算一次，然后保存起来。

好了，今天我们对于递归问题的讨论就到此结束了，还请大家重点思考和回顾一下我们构建的整个过程。