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)