函数递归

定义

如果一个函数在内部调用自己，那么这个函数就是递归函数

特点

  1. 定义简单
  2. 改变的是参数，而不变的的是函数本身

使用

  1. # 直接调用自己
  2. def index():
  3.     print("from function index")
  4.     index()
  5. """"
  6. RecursionError: maximum recursion depth exceeded while calling a Python object
  7. """
  8. # python解释器自带的应急机制，当最大递归深度超出限制了，就会停止
  1. # 对python最大递归深度,官方给出的是1000
  2. import sys
  3. print(sys.getrecursionlimit())  # 获取默认的最大递归深度  
  4. # 1000
  5. sys.setrecursionlimit(2000)  # 还可以修改最大递归深度
  6. print(sys.getrecursionlimit()) 
  7. # 2000
  1. # 间接调用自己
  2. def index_1():
  3.     print("from function index_1")
  4.     index_2()
  7. def index_2()
  8.     print("from function index_2")
  9.     index_1()
  11. index_2()
  1. # 递归实现
  2. def num(n):
  3.     if n == 1:
  4.         return 'kevin'
  5.     return num(n - 1)
  8. print(num(5))
  9. # num(5)=num(5-1)  第一次进入
  10. # num(4)=num(4-1)  第二次进入
  11. # num(3)=num(3-1)  第三次进入
  12. # num(2)=num(2-1)  第四次进入
  13. # num(1)='kevin'   第五次进入，满足条件终止
  15. # num(n)=num(n-1)  n>1 递归终止条件
  16. # num(1)='kevin'   n=1 等于终止的条件

要求

  1. 必须是自己调用自己
  2. 必须有一个明确的递归结束条件，即为递归出口

回溯与递推

递推

像上边递归实现所拆解，递归每一次都是基于上一次进行下一次的执行，这叫递推

回溯

在遇到终止条件，则从最后往回返一级一级的把值返回来，这叫回溯

实例

  1. # 需求:循环打印出列表中每一个数字
  2. l = [1, 2, [3, [4, 5, 6, [7, 8, [9, 10, [11, 12, 13, [14, 15, [16, [17, ]], 19]]]]]]]
  5. def get_num(l):
  6.     for i in l:
  7.         if isinstance(i ,int):  # 判断某个数据是否属于某个类型
  8.             print(i)
  9.         else:
  10.             get_num(i)
  12. get_num(l)
  1. # 阶乘
  2. def num(n):
  3.     if n == 1:
  4.         return 1
  5.     return num(n - 1) * n
  8. print(num(5))
  9. # 120

算法之二分法

什么是算法

算法是利用计算机解决问题的处理步骤，即算法就是解决问题的步骤

为什么要学习算法

提高自身的编程能力以外，又能对自己的思维有一定的提升，也使程序提高效率

算法之二分法

二分法是算法里面最入门的一个，主要是感受算法的魅力所在

  1. """二分法使用有前提: 数据集必须有先后顺序(升序 降序)"""
  2. # 查找列表是否存在某一值,
  3. l_num = [13, 21, 35, 46, 52, 67, 76, 87, 99, 123, 213, 321, 432, 564, 612]
  6. def num(l, n):
  7.     if len(l) == 0:  # 列表只剩一个值，结束条件
  8.         print("不存在")
  9.         return
  10.     middle_index = len(l) // 2  # 1.将列表的中间索引值取出（只能是整数）
  11.     if n > l[middle_index + 1]:  # 2.判断中间索引对应的值与目标的大小
  12.         l_right = l[middle_index + 1:]  # 3.用切片保留右侧数据
  13.         print(l_right)  # 输出右侧列表
  14.         num(l_right, n)  # 4.将右侧数据列表，和原有值再次带入调用自身函数
  15.     elif n < l[middle_index]:  # 5.判断中间索引对应的值与目标的大小
  16.         l_left = l[:middle_index]  # 6.用切片保留左侧数据
  17.         print(l_left)  # 输出左侧列表
  18.         num(l_left, n)  # 7.将左侧数据列表，和原有值再次带入调用自身函数
  19.     else:
  20.         print("存在")
  23. num(l_num, 123)
  24. # [99, 123, 213, 321, 432, 564, 612]
  25. # [99, 123, 213]
  26. # 存在

二分法的缺陷

  1. 如果要找的元素就在数据集的开头，二分更加复杂
  2. 数据集必须有顺序

目前没有最完美的算法 都有相应的限制条件，python更多算法，二分法 快排 插入 冒泡 堆排序