递归
- 如果一个函数在内部调用了自身,这个函数称为递归函数
- 递归条件:
1.子问题与原始问题为同样的事,且更为简单
2.不能无限制的调用本身,要有个出口,化简为非递归状况处理
- 高斯求和问题:
def sum_number(n):
total = 0
for i in range(0,n+1):
total += i
sum_number(100)
如果用递归来写:
def sum_number(n):
if n<=0:
return 0
return n+sum_number(n-1)
sum_number(100)
- 递归核心:每一次递归,整体问题都要比原来减小,并且递归到一定层次时,要能直接给出结果。
- 基本步骤:
1.初始化算法。递归程序通常需要一个开始时使用的种子值,可以向函数传递参数,或者提供一个入口函数,这个函数是非递归的,但可以为递归计算设置种子值。
2.检查要处理的当前值是否已经与基线条件匹配。如果匹配,则进行处理并返回值
3.使用更小的或者更简单的子问题来重新定义答案。
4.对子问题进行算法
5.将结果合并入答案的表达式
6.返回结果
- 注意:使用递归函数要放置递归深度溢出,在Python中,通常情况下,这个深度为1000层,超过将抛出异常。在计算机中,函数递归调用是通过栈(stack)这种数据结构实现的,每当进入一个递归时,栈就会加一层,每当函数返回一次,栈就减少一层。由于栈的大小不是无线的,所以,递归调用的次数过多,会导致栈溢出。
尾递归
- 简介:
1.当递归调用是整个函数体最后执行的语句且它的返回值不属于表达式的一部分时,就是尾递归
2.特点:在回归过程中不做任何操作。
3.原理:当编译器检测到一个函数调用是尾递归的时候,它就覆盖当前的活动记录而不是在栈中去创建一个新的。实际运行效率更高。
- 以尾递归方式实现阶乘函数:
def facttail(n,res):
if n < 0:
return 0
elif n == 0:
return 1
elif n == 1:
return res
else:
return facttail(n-1,n*res)
只是比递归多了一个参数res。res(初始化为1)维护递归层次的深度。
匿名函数
Python用lambda关键字来创建匿名函数。所谓匿名,即不在用def语句来定义一个标准函数
1.lambda只是一个表达式,而不是一个代码块,函数体比def简单
2.仅仅能在lambda表达式中封装有限的逻辑
3.lambda函数拥有自己的命名空间
4.形式:lambda 参数:表达式
5.匿名函数可以赋值给一个变量,在利用变量来调用该函数
>>>f = lambda x:x*x
>>>f(6)
36
6.可以把匿名函数作为别的函数返回值返回
推导式
1.列表推导式
- 快速生成列表:
lis = [x*x for x in range(1,11)]
相当于:
lis = []
for x in range(1,11):
lis.append(x*x)
- 增加条件语句
>>>[x*x for x in range(1,11) if x%2 == 0]
[4,16,36,64,100]
- 多重循环
>>>[a+b for a in '123' for b in 'abc']
['1a','1b','1c','2a','2b','2c','3a','3b','3c']
2.字典推导式
>>> dic = {x:x**2 for x in (2,4,6)}
{2:4,4:16,6:36}
>>> type(dic)
<class 'dict'>
中间的:
表示左边是key右边是value
3.集合推导式
大括号除了能作字典推导式,还可以用作集合推导式。细微差别
>>> a = {x for x in 'abcrabiaac' if x not in 'abc'}
>>> a
{'r','i'}
>>> type(a)
<class 'set'>
4.没有元组推导式,没有元组推导式,没有元组推导式
面试题:
看下面代码输出结果是什么?为什么?
result = [lambda x:x+i for i in range(10)]
print(result[0](10))
结果:result0~9的结果都是19
函数具有调用时才查找变量的特性。在你没有调用它之前,不不会保存也不关心它内部变量的具体值。只有当你调用它的时候,才回去逐一找变量的具体值。
result[0]被调用的时候,变量i已经循环完毕,变成9了。
- 想要i循环的值怎么办?
不要引用上层变量,把i直接传进来
result = [lambda x,i=i:x+i for i in range(10)]
迭代器
迭代器是一种可以被遍历的对象,并且能作用与next()函数。迭代器对象从集合的第一个元素开始访问,直到所有的元素被访问完结束。
迭代器只能往后遍历,不能回溯。两个方法:iter()
和next()
- 创建
lis = [1,2,3]
it = iter(lis) //创建
next(it) //取出下一个元素
- 迭代器(Iterator)和可迭代(Iterable)的区别
1.凡是可用作for循环的对象都是可迭代类型
2.凡是作用于next()函数的对象都是迭代器类型
3.list,dict,str等是可迭代的但不是迭代器,因为next()函数无法调用,可以通过iter()函数转换成迭代器
4.for循环的本质就是不断调用next()函数实现的。