函数递归

定义

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

特点

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

使用

# 直接调用自己
def index():
    print("from function index")
    index()
""""
RecursionError: maximum recursion depth exceeded while calling a Python object
"""
# python解释器自带的应急机制,当最大递归深度超出限制了,就会停止
# 对python最大递归深度,官方给出的是1000
import sys
print(sys.getrecursionlimit())  # 获取默认的最大递归深度  
# 1000
sys.setrecursionlimit(2000)  # 还可以修改最大递归深度
print(sys.getrecursionlimit()) 
# 2000
# 间接调用自己
def index_1():
    print("from function index_1")
    index_2()
    
    
def index_2()
    print("from function index_2")
    index_1()
 
index_2()
# 递归实现
def num(n):
    if n == 1:
        return 'kevin'
    return num(n - 1)


print(num(5))
# num(5)=num(5-1)  第一次进入
# num(4)=num(4-1)  第二次进入
# num(3)=num(3-1)  第三次进入
# num(2)=num(2-1)  第四次进入
# num(1)='kevin'   第五次进入,满足条件终止

# num(n)=num(n-1)  n>1 递归终止条件
# num(1)='kevin'   n=1 等于终止的条件

要求

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

回溯与递推

递推

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

回溯

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

实例

# 需求:循环打印出列表中每一个数字
l = [1, 2, [3, [4, 5, 6, [7, 8, [9, 10, [11, 12, 13, [14, 15, [16, [17, ]], 19]]]]]]]


def get_num(l):
    for i in l:
        if isinstance(i ,int):  # 判断某个数据是否属于某个类型
            print(i)
        else:
            get_num(i)

get_num(l)
# 阶乘 
def num(n):
    if n == 1:
        return 1
    return num(n-1)*n

算法之二分法

什么是算法

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

为什么要学习算法

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

算法之二分法

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

"""二分法使用有前提: 数据集必须有先后顺序(升序 降序)"""
# 取出列表l数字123,
l_num = [13, 21, 35, 46, 52, 67, 76, 87, 99, 123, 213, 321, 432, 564, 612]


def num(l, n):
    if len(l) == 0:  #  列表只剩一个值,结束条件
        print("没找到")
        return
    middle_index = len(l) // 2  # 1.将列表的中间索引值取出(只能是整数)
    if n > l[middle_index + 1]:  # 2.判断中间索引对应的值与目标的大小
        l_left = l[middle_index + 1:]  # 3.用切片保留左侧数据
        print(l_left)  # 输出左侧列表
        num(l_left, n)  # 4.将左侧数据列表,和原有值再次带入调用自身函数
    elif n < l[middle_index]:  #  5.判断中间索引对应的值与目标的大小
        l_right = l[:middle_index]   # 6.用切片保留左侧数据
        print(l_right)  # 输出右侧列表
        num(l_right, n)  # 7.将右侧数据列表,和原有值再次带入调用自身函数
    else:
        print("找到了", n)


num(l_num, 123)
# [99, 123, 213, 321, 432, 564, 612]
# [99, 123, 213]
# 找到了 123

二分法的缺陷

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

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

Last modification:March 22, 2022
如果觉得我的文章对你有用,请随意赞赏