python：算法——递归算法

1、什么是递归算法

​ 在计算机中，程序调用自身的编程技巧我们称之为递归算法。那么再通俗一点来讲就是：在某个python文件中，有一个函数，这个函数可以在自己的函数体内根据条件，自己调用自己的函数，那么这样自身调用自身的过程或者说行为，我们称之为递归。

2、递归的详细理解

​ （1）假设，有一个直线型的迷宫（只有一条路，不能拐弯），迷宫中有一份藏宝图。

​ （2）那么，有一天我来到迷宫入口，那么当我进入这个迷宫的大门的时候。我们就可以理解为：就是在程序中的某个地方调用了该函数。

​ （3）当你进入迷宫以后，惊奇的发现还要一个门，那么你就再打开这个门进入。当你打开这个门的时候，就可以理解为：在该函数体中，它自己开始调用自己

​ （4）当你进入这个门以后，你又发现里边还要一个门，于是打开门，这个时候又发现了一个门，就这样你循环往复，一直是一个行为（打开门然后进入）。这里我们就可以理解为，在该函数体内，这个函数一直调用自己。

​ （5）这样，经过了很久，你打开了一道门，发现里边没有其他的门了，并且只一个盒子，那么你打开这个盒子，拿到了藏宝图。这个时候就可以理解为递归到了出口的地方，或者说递归到了一定次数了。

​ （6）最后，你带着这个藏宝图要离开这个鬼地方，那么你就要原路返回，因为这是一个直线型的迷宫，没有其他的路了，所以你带着藏宝图不断的走出一个个的门，最终从迷宫中出来了。那么，这个过程我们就可以理解为函数已经递归到了该函数的出口条件这里，并且，要带着出口条件中的值（次数）往回返，通过这个次数和在该函数体内部调用自己时设置的规律，找到其他的值，并且将这些值做一定的处理。

3、递归图解

4、为什么要使用递归

​ （1）如果不使用递归，而使用循环，那么代码量会比较多

​ （2）使用循环实现的那么程序不容易理解，但是使用递归就会好理解很对

​ （3）如果使用循环，程序的性能可能更高，如果使用递归，程序更容易理解，所以如何选择什么对你来说更重要

5、递归的特征

​ （1）要实现递归必须有一个函数

​ （1）并且在这个函数体内要自己调用自己

​ （3）递归必须要有一个深度，也就是判断条件,这个判断条件是判断次数或者说个数的

​ （7）到达一定的深度后必须返回一个东西，哪怕是空的也可以，目的是结束递归

​ （8）未到达一定深度时，可以返回该函数，但同时也可以不返回，这个根据需求而定，但是必须不断调用函数自身

5、经典案例

（1）使用递归算法求n！

需求：

​ 用户输入一个数字，那么就算该数字的阶乘，并打印出来

分析：

​ （1）我们可以将用户输入的数字或者这个题看成是一个列表，那么该列表的长度就是 n

​ （2）此时我们知道了列表的第一个元素为1，最后一个元素为n，那么要计算1-n之间的元素相乘

​ （3）那么就必须 n-1，找到前边的元素的值

​ （4）当 n == 1的时候，就到了该列表的第一个位置了，所以就不能再往前了

​ （5）因为计算机不知大第一个元素是啥，那么我们就要返回一个1，来告诉计算机

​ （6）最后计算机根据递归的出口值，以及函数递归的规律，进行计算

​ （7）最后返回你想要的结果

# 函数必须第一个参数，这个参数的作用是你求取第几个数字的阶乘
def func(n):
    # 因为我们只知道任何数字的阶乘最后都要 * 1，那么这就是递归深度或者说次数
    if n == 1:
        # 那么我们就返回 1，将1返回给调用它的人，就是下面的函数调用
        return 1
    else:
       # 因为n！= n * n-1 ...*1,那么5！= 5*4！
        return n * func(n-1)

if __name__ == '__main__':
    # 求5的阶乘，传入一个递归次数5
    result = func(5)
    # 打印结果
    print(result)

（2）使用递归求岁数

需求：

​ 有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后问第一个人，他说是10岁。请问第五个人多大？

分析：

​ （1）因为是5个人，那么我们就可以看作为长度为5的列表

​ （2）并且这个列表中存储了1-5个人的年龄，第五个元素为10，而剩下人的年龄都是在它后边的人的年龄上+2

​ （3）那么我们可以将这个假设的列表反转，将第五个人的年龄变为第一个，也就是10在第一个索引位置，而剩下人的年龄都变为它前边人的年龄+2

​ （4）那么我们可以将第一个人和他的年龄作为递归的深度，和返回的值

​ （5）而剩下人都是 n-1，拿到前一个元素的值，在基础上+2

​ （6）最后返回的就是第五个人的年龄，反转过来其实就是第一个人的年龄

def func(n):
    # 当递归到第一个人的年龄时，说明到了指定深度
    if n == 1:
        # 返回第一个人的年龄10
        return 10
    else:
        # 当没有到达递归深度，就继续拿到上一个人的年龄，并在此基础上+2，最后返回的就是第5个人的年龄，反转过来就是第一个人的年龄
        return 2 + func(n-1)

if __name__ == '__main__':
    # 长度为5
    age = func(5)
    print(age)

（3）使用递归反输出

需求：

​ 利用递归函数调用方式，将所输入的5个字符，以相反顺序打印出来

分析：

​ （1）首先是打印，那么当没有打到达递归深度时就不反悔值了，而是输出，再调用函数自身

​ （2）并且这5个字符我们都知道了，所以到达递归深度后，什么也不需要返回，直接 return 终止该函数就行

​ （3）那么为了存储这5个元素，要将其存入列表，通过列表去取值

def func(n):
    # 当递归到索引为0的时候
    if n == 0:
        # 终止该函数
        return
    # 当没有递归到指定深度时
    else:
        # 要输出列表中的值，因为列表比长度少1，索引必须-1才能拿到对应的值，那么输出的时候的顺序为从后往前
        print(mylist[n-1])
        # 递归次数
        func(n-1)


if __name__ == '__main__':
    # 定义一个空列表
    mylist = []
    # 使用for循环来拿到5个字符，并将5个字符存入列表中
    for i in range(1,6):
        mystr = input(f"请输入第{i}个字符：")
        mylist.append(mystr)
     # 传入列表的长度，因为列表的长度为5，那么也就是5个字符
    func(len(mylist))

（4）使用递归求斐波那契数列

需求：

​ 使用递归算法，求指定位数的斐波那契数列

分析：

​ （1）斐波那契数列是典形的兔子数列，第一位和第二位为1，从第三位开始，前两项的和等于第三项

​ （2）那么我们可以将指定位数n看作为列表的长度，而列表的第一位和第二位为1，然后从第三位开始每一个元素的值为前两项元素的和

​ （3）那么递归的出口就是1或者2，出口返回的值为1，然后递归调用函数的参数为 n-1 + n-2，也就是第三项的值，或者说我们求的指定位数的值。

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

if __name__ == '__main__':
    result = func(5)
    print(result)

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

if name == ‘main’:
result = func(5)
print(result)