【Python】 ---- Python的函数和递归

落日映苍穹つ 2023-07-03 08:13 120阅读 0赞

## 函数 ##

**1、Python中函数的使用**  
使用函数的好处：  
1、避免代码的冗余  
2、让程序代码结构更加清晰  
3、让代码具有复用性，便于维护  
函数定义的格式：

def 函数名（参数列表）:
          函数体

# 1、编写一个最简单的函数
    def sayHello():
        print('hello')
    # 调用函数
    sayHello()
    
    # 2、带有参数的函数
    def sayHello2(name):
        print('你好', name)
    sayHello2('北京')
    
    # 3、带有返回值的函数
    # 1累加和到任意一个整数
    def caculateNum(num):
        # 存储累加和
        sumNum = 0
        for i in range(1, num+1):
            sumNum = sumNum + i
        # 返回sumNum
        return  sumNum
    res = caculateNum(100)
    print(res)

函数中使用断言  
格式：assert 表达式 \[ , 参数\]  
当表达式为假时，抛出AssertionError错误，并将参数输出

def div(s):
        # 转化成整型
        n = int(s)
        # 判断传入的参数是否合法，表达式为真时才能往下执行
        assert n != 0, 'n is zero'
        return 10/n
    print(div('0'))

**2、匿名函数**  
1、关键字lambda表示匿名函数，冒号前面的n表示函数参数，可以有多个参数。  
2、匿名函数有个限制，就是只能有一个表达式，不用写return，返回值就是该表达式的结果。  
3、用匿名函数有个好处，因为函数没有名字，不必担心函数名起冲突。此外，匿名函数也是一个函数对象，也可以把匿名函数赋值给一个变量，再利用变量来调用该函数：有些函数在代码中只用一次，而且函数体比较简单，使用匿名函数可以减少代码量，看起来比较“优雅”。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70]

# 匿名函数
    # lambda parameter_list: expression
    # 参数列表没有个数的限制，但是表达式只能有一个
    cal = lambda x, y: x*y
    print(cal(2, 3))
    
    def calc(x, y):
        if x >= y:
            return x/y
        else:
            return x*y
    print(calc(4, 2))
    
    # 将上述代码用匿名函数的方式
    # 三元表达式
    # 为True时返回的内容 if 为True的条件 else False时返回的内容
    calc2 = lambda x, y: x/y if x >= y else x*y
    print(calc2(4, 2))

## 系统高阶函数 ##

**1、map()函数**  
map(func, iterable) 将可迭代对象依次传递给func处理，最后把处理的结果作为新的可迭代对象返回

# map()函数
    def power(x):
        return x*x
    # 传递的是函数名
    res = map(power, [1, 2, 3, 4, 5])
    # res返回的是一个生成器
    print(list(res))
    # [1, 4, 9, 16, 25]
    
    # 使用lambda表达式
    print(list(map(lambda x: x*x, [1, 2, 3, 4, 5])))

**2、reduce()函数**  
reduce(func, iterable)函数：累积操作。func函数必须接受两个参数，reduce会把func的运行结果做一个参数，然后从iterable中再依次取出一个数据当作另一个参数。

# reduce函数
    # python 3.0以后, reduce已经不在built-in function里了, 要用它就得from functools import reduce
    from functools import reduce
    li = [1, 2, 3, 4]
    res = reduce(lambda x, y: x*y, li)
    # 1 * 2 = 2
    # 2 * 3 = 6
    # 6 * 4 = 24
    print(res)
    
    # 例一： [1, 3, 5, 7, 9] ----> 13579
    def func(x, y):
        return x*10 + y
    print(reduce(func, [1, 3, 5, 7, 9]))
    
    # 例二：传入的参数是 '13579' -----> 13579
    # str -----> int
    digits = { '0':0, '1':1,'3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9}
    def StrToInt(s):
        def fn(x, y)
            return 10*x + y
        def CharToNum(s):
            return digits[s]
        return reduce(fn, map(CharToNum, s))
    print(StrToInt('13579'))

**3、filter() 函数**  
filter(func, iterable) 根据func来过滤iterable，将iterable中的数据传入func中，如果函数返回True则保留该数据，否则就不保留

li = [1, 2, 3, 4, 5, 6, 7]
    把所有的奇数过滤出来
    print(list(filter(lambda x: x%2 == 1, li)))

**4、sorted() 函数**  
sorted(iterable, key = None, reverse = False) 对数据进行排序，并返回一个新对象，原对象不变。key可以用来指定排序的规则，它接受的值是一个函数。reverse是指定排序的顺序（升序或降序），默认为升序。

列表推导式
    li = []
    for i in range(10):
        li.append(i)
    print(li)
    # 快速生成一个列表
    print([i for i in range(10)])
    
    # 引入随机数模块
    from random import randint
    # 生成-10到10之间的随机数
    li = [randint(-10, 10) for _ in range(5)]
    print(li)
    # 排序
    res1 = sorted(li)
    print(res1)
    
    # 加入key：按照绝对值排序
    res2 = sorted(li, key=abs)
    print(res2)
    
    # 降序排序
    res3 = sorted(li, key=abs, reverse=True)
    print(res3)

## 递归 ##

**什么是递归：**  
1、递归不是算法，但用途很大  
2、递归的定义：函数内部调用函数本身  
3、递归这种技术在很多算法中都存在：回溯法，动态规划，分治法等  
接下来以斐波那契数列为例使用递归去实现它：  
斐波那契数列（Fibonacci sequence），又称黄金分割数列、兔子数列。斐波那契数列为1、1、2、3、5、8、13、21、34……此数列从第3项开始，每一项都等于前两项之和，递推公式为F(n)=F(n-1)+F(n-2)，n≥3，F(1)=1，F(2)=1。

# 使用递归编写斐波那契数列
    def fibo(k):        # k 代表位置序号
        assert k > 0, 'k值必须大于0'
        if k in [1, 2]:
            return 1
        return fibo(k-1) + fibo(k-2)
    print(fibo(9))

然后，我们再用循环实现斐波那契数列从而更加深入的了解一下：

使用循环实现斐波那契数列
    def fibo(k):
        assert k > 0, 'k必须大于0'
        if k in [1, 2]:
            return 1
        before1, before2 = 1, 1
        # 循环的目的就是不断更新before1, before2
        for _ in range(3, k+1):
            temp = before1
            res = before1 + before2
            before1 = res
            before2 = temp
        return res
    print(fibo(9))

## 练习 ##

使用递归实现二分查找算法。  
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。  
算法思想：首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

# 二分查找
    # 生成数据
    from random import randint, choice
    data = [randint(1, 100) for _ in range(10)]
    # 随机选择一个
    target = choice(data)
    data = sorted(data)
    print('有序数组是', data)
    print('要查找的目标值是', target)
    # 使用递归实现二分查找
    def BinarySearch(left, right, data_list, target):
        """ left：序列最左边的序号 right：序列最右边的序号 data_list：要查找的列表 target：要查找的那个数 """
        # 求中间序号值
        mid = int((left + right)/2)
        if data_list[mid] == target:
            return mid
        # 中间的数字比目标值小，往右找
        elif data_list[mid] < target:
            return BinarySearch(mid+1, right, data_list, target)
        # 中间的数字比目标值大，往左找
        else:
            return BinarySearch(left, mid-1, data_list, target)
    res = BinarySearch(0, len(data)-1, data, target)
    print(res)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200205103723835.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg==,size_16,color_FFFFFF,t_70