python学习week5-递归,匿名函数、生成器

时间:2021-09-09 19:16:06

1、递归函数

1.1、递归函数的限制

  (1)递归一定要有退出条件,并且递归调用一定要执行到这个退出条件;如果没有退出条件,就是无限调用,会耗尽所有资源(栈空间);

  (2)递归调用的深度不易过深,Python对递归调用的深度做了限制,以保护解释器;

1.2、递归实例

①、递归实现斐波拉契数列

# version1:数学公式版本
def fib(n):
    return 1 if n<3 else fib(n-1)+fib(n-2)

print(fib(10))

分析:此版本虽然看着简洁明了,但是会有很大的效率问题,当n操作35以后计算结果就非常慢

# version2:利用上一次结果
def fib(n,a=0,b=1): # n=3
    if n<3:
        return a+b
    else:
        a,b=b,a+b  # 0,1=1,1
        return fib(n-1,a,b)

分析:版本每次都利用了上一次运算的结果,所以效率相对于第一个版本来说,快了不少;

# for循环实现
a,b=0,1
for i in range(10):
    a,b=b,a+b
    print(a)

分析:版本二就是根据for循环演变而来

②、递归实现阶乘

def fac(n,sum=1):
    if n==1:
        return 1
    return n*fac(n-1)

def fac(n,sum=1):
    sum=sum*n
    if n<2:
        return sum
    return fac(n-1,sum)

# 版本二将每次计算的结果带入了下一次计算

③、将一个数逆序放入列表

nums='1234'
print(nums[len(nums)-1])
l=[]
# for循环实现
for i in range(len(nums)-1,-1,-1):
  l.append(nums[i])

print
(l)

# 列表拼接实现
def revert(x): if x == -1: return [] return [nums[x]] + revert(x-1) print(revert(len(nums)-1))
# 字符串切片实现
def revert(x,target=[]): if x: target.append(x[-1]) revert(x[:-1]) return target print(revert(nums))

④、递归解决猴子吃桃问题

'''
x
d1=x//2-1
d2=d1//2-1
d3=d2//2-1
...
...
d9=d8//2-1 ==> 2(d9+1)=d8=d7/2-1
'''
peach=1
for i in range(9):
    peach=2*(peach+1)
print(peach)

'''
这题得倒着推。第10天还没吃,就剩1个,说明第9天吃完一半再吃1个还剩1个,假设第9天还没吃之前有桃子p个,可得:p * 1/2 - 1 = 1,可得 p = 4。以此类推,即可手算出。
代码思路为:第10天还没吃之前的桃子数量初始化 p = 1,之后从9至1循环9次,根据上述公式反推为 p = (p+1) * 2 可得第1天还没吃之前的桃子数量。
for循环中的print()语句是为了验证推算过程而增加的。代码如下:
p = 1 print('第10天吃之前就剩1个桃子') for i in range(9, 0, -1): p = (p+1) * 2 print('第%s天吃之前还有%s个桃子' % (i, p)) print('第1天共摘了%s个桃子' % p) ''' # 递归实现 def peach(n=10): if n == 1: return 1 return (peach(n-1)+1)*2 print(peach())

2、匿名函数

#  匿名函数:即没有名字的函数;

  没有名字如何定义?

  没有名字如何调用?

# Pyhton借用lambda表达式解决以上问题;

# 格式: lambda 参数列表:表达式 # 此表达式相当于函数体内的return 后面的语句;

# 特点:

  ①:使用lambda关键字来定义匿名函数;

  ②:参数列表不需要小括号;

  ③:冒号是用来分割参数列表和表达式的;

  ④:不需要使用return,表达式的值,就是匿名函数的返回值;

  ⑤:lambda表达式只能写在一行上,也被称为单行函数;(函数体内逻辑复杂的不适用);

  ⑥:一般用于高阶函数传参时,可以简化代码;

#  自定义函数可以改写为lambda形式;

def fun(x,y):
    return x+y

f=lambda x,y:x+y # 不建议这么用;
# (1)相当于给lambda函数赋值函数名f,
# (2)函数f的功能与fun函数的功能一样,即fun函数可以改写为下面lambda形式;

print(fun)
print(f)
'''
<function fun at 0x000001CD55452E18> 
<function <lambda> at 0x000001CD558A9D08>
'''
l=[x for x in (lambda *args:map(lambda x:x+1,args))(*range(5))]
'''
分析: 
(*range(5)) 先解构为(0,1,2,3,4) 传递给 *args, 然后执行map里面的函数;
map(func,iter)  ==> func=lambda x:x+1 iter=args, 然后x向iter也就是args中取值
[0,1,2,3,4] 经过func处理后返回为[1,2,3,4,5]
'''
print(l) # [1, 2, 3, 4, 5]

l=[x for x in (lambda *args:map(lambda x:(x+1,args),args))(*range(5))]
'''
分析:这个实例和上一个差不多,只是在内层lambda返回类型变了,返回的为一个二元组(x+1,args),这个的args=iter=(0,1,2,3,4)
'''
print(l)
[(1, (0, 1, 2, 3, 4)), (2, (0, 1, 2, 3, 4)), (3, (0, 1, 2, 3, 4)), (4, (0, 1, 2, 3, 4)), (5, (0, 1, 2, 3, 4))]
s = "this is\na\ttest"
l=lambda x:' '.join(x.split())
print(l(s)) # 运行结果:this is a test

c = lambda **Arg: Arg
print(c()) # 返回一个空字典;

3、生成器与迭代器

3.1、迭代器

  # 迭代:是一个重复的过程,每一次重复都是基于上一次的结果而来;

  # 可迭代对象:凡是可调用__iter__方法的,都是可迭代对象(iterable);

3.2、迭代器与可迭代对象的区别

  ①:凡是可用于for循环的对象,都是可迭代对象;

  ②:凡是可以作用于next()函数的对象,都是迭代器对象;

  ③:list、dict、str、等都是可迭代对象,并不是迭代器对象,因为next()函数无法调用他们,可以使用iter()函数将他们转换为迭代器对象;

3.3、for循环的原理

# 基于for循环可以完全不依赖索引取值;

d={'a':1,'b':2,'c':3}
for k in d:
    print(d[k])
'''
1、执行in后对象的dic.__iter__()方法,得到一个迭代器对象iter_dic
2、执行next(iter_dic),将得到的值赋值给k; ==> d.__iter__().__next__() ==> k='a'然后执行循环体代码;
3、重复过程2,知道捕获异常StopIteration,循环结束;
'''

3.4、生成器generator:

  ①:生成器指的是生成器对象,可以由生成器表达式得到,也可以使用yield关键字得到一个生成器函数,调用这个函数可以得到一个生成器对象;

3.5、生成器函数:

  ①:函数体中包含yield语句的函数,返回生成器对象;

  ②:生成器对象是一个可迭代对象,也是一个迭代器;

  ③:生成器对象是延迟计算,惰性求值; # 节省内存空间;

  ④:在 Python中,使用yield返回的函数会变成一个生成器(generator)。在调用生成器的过程中,每次遇到yield时函数会暂停并保存当前所有的运行信息,返回yield的值。并在下一次执行next()方法时从当前位置继续运行。

'''
斐波拉切数列生成器实现
'''
def fib(n,a=0,b=1):
    for i in range(n):
        a,b=b,a+b
        yield a
g=fib(10)

for i in g:
    print(i)

#################
def fib(n,a=0,b=1):
    count=0
    while count<n:
        a,b=b,a+b
        count+=1
        yield a

for i in fib(10):
    print(i)

 # yield 和return的功能类似,都可以返回值;但是不同的是return只能返回一次值,而yield可以返回多次值;(能够直接返回到函数内部,非常牛逼的功能)

def foo(count:int):
    print('start...')
    while True:
        yield count
        count+=1

g=foo(10)
print('===>第一次next')
print(next(g))
print('===>第二次next')
print(next(g))
print('===>第三次next')
print(next(g))

'''
===>第一次next
start...
10
===>第二次next
11
===>第三次next
12
'''

4、插入排序

# 插入排序分析

[0,1,9,8,5,6] 原始数列
哨兵每次从无序区拿第一个作为哨兵

[9,1,9,8,5,6] 
第一趟:设定哨兵位等于s=9 ,有序区:1  无序区:9,8,5,6
拿有序区1和无序区9 比较大小 , 1 不大于9  所以位置不改变, 比较后 有序区为:1,9  无序为:8,5,6;

[8,1,9,8,5,6] 
第二趟:s=8, 有序区为:1,9  无序为:8,5,6; 
拿有序区9和无序8比较,9 > 8  => [8,1,9,9,5,6] =>j-1 => [8,1,8,9,5,6]

[5,1,8,9,5,6]
第三趟:s=5 ,有序1,8,9  无序:5,6
9>5 ==> [5,1,8,9,9,6] ==> 8>5 ==> [5,1,8,8,9,6] ==> 1不大于5 ==>[5,1,5,8,9,6]

总结:每次比较将无序区域第一个数拿来作为比较的哨兵,然后将有序区数和哨兵依次比较,比哨兵大的数往后放,
直到比较到比哨兵小,然后将哨兵插入队列
######代码实现############
def insert_Sort(l,nums=[0]): # nums=[0,1,9,8,5,6]
    '''
    实现插入排序
    :param l:
    :return:
    '''
    nums=nums+l
    for i in range(2,len(nums)): # i=3
        nums[0]=nums[i] #  num[0]=8
        j=i-1        
        if nums[j] > nums[0]:
            while nums[j] > nums[0]:
                nums[j+1]=nums[j] 
                j-=1  
            nums[j+1]=nums[0]  # 插入哨兵
    return nums[1:]

l=[1,9,8,5,6]
res=insert_Sort(l)