还记得在《迭代》中提到的那几个说出来就让人感觉牛X的名词吗?前面已经学习过“循环”、“遍历”和“迭代”了。现在来看“递归”。
递归
什么是递归?
这是对“递归”最精简的定义。还有故事类型的定义.
如果用上面的做递归的定义,总感觉有点调侃,来个严肃的(选自维基百科):
最典型的递归例子之一是斐波那契数列,虽然前面用迭代的方式实现了它,但是那种方法在理解上不很直接。如果忘记了这个数列的定义,可以回到《练习》中查看。
根据斐波那契数列的定义,可以直接写成这样的斐波那契数列递归函数。
#!/usr/bin/env python
# coding=utf-8
def fib(n):
"""
This is Fibonacci by Recursion.
"""
if n==0:
return 0
elif n==1:
return 1
else:
return fib(n-1) + fib(n-2)
if __name__ == "__main__":
f = fib(10)
print f
把上述代码保存。这个代码的意图是要得到n=10的值。运行之:
$ python 20401.py
55
fib(n-1) + fib(n-2)
就是又调用了这个函数自己,实现递归。为了明确递归的过程,下面走一个计算过程(考虑到次数不能太多,就让n=3)
- n=3,fib(3),自然要走
return fib(3-1) + fib(3-2)
分支 - 先看fib(3-1),即fib(2),也要走else分支,于是计算
fib(2-1) + fib(2-2)
- fib(2-1)即fib(1),在函数中就要走elif分支,返回1,即fib(2-1)=1。同理,容易得到fib(2-2)=0。将这两个值返回到上面一步。得到
fib(3-1)=1+0=1
- 再计算fib(3-2),就简单了一些,返回的值是1,即fib(3-2)=1
- 最后计算第一步中的结果:
fib(3-1) + fib(3-2) = 1 + 1 = 2
,将计算结果2作为返回值
从而得到fib(3)的结果是2。
从上面的过程中可以看出,每个递归的过程,都是向着最初的已知条件a0=0,a1=1
方向挺近一步,直到通过这个最底层的条件得到结果,然后再一层一层向上回馈计算机结果。
其实,上面的代码有一个问题。因为a0=0,a1=1
是已知的了,不需要每次都判断一边。所以,还可以优化一下。优化的基本方案就是初始化最初的两个值。
#!/usr/bin/env python
# coding=utf-8
"""
the better Fibonacci
"""
meno = {0:0, 1:1} #初始化
def fib(n):
if not n in meno: #如果不在初始化范围内
meno[n] = fib(n-1) + fib(n-2)
return meno[n]
if __name__ == "__main__":
f = fib(10)
print f
#运行结果
$ python 20402.py
55
以上实现了递归,但是,至少在python中,递归要慎重使用。在一般情况下,递归是能够被迭代或者循环替代的,而且后者的效率常常比递归要高。所以,我个人的建议是,对使用递归要考虑的周密一下,不小心就永远运行下去了。
几个特殊函数
前面已经知道了如何编写、调用函数。此外,在python中,有几个特别的函数,很有意思,它们常常被看做是python能够进行所谓“函数式编程”的见证。
不管读者是初学还是老油条,都建议将上面这段话认真读完,不管理解还是不理解,总能有点感觉的。
正如前面引文中所说的,python是支持多种范型的语言,可以进行所谓函数式编程,其突出体现在有这么几个函数:
filter、map、reduce、lambda、yield
有了它们,最大的好处是程序更简洁;没有它们,程序也可以用别的方式实现,只不过麻烦一些罢了。所以,还是能用则用之吧。更何况,恰当地使用这几个函数,能让别人感觉你更牛X。
(注:本节不对yield进行介绍,请阅读《生成器》)
lambda
lambda函数,是一个只用一行就能解决问题的函数,听着是多么诱人呀。看下面的例子:
>>> def add(x): #定义一个函数,将输入的变量增加3,然后返回增加之后的值
... x += 3
... return x
...
>>> numbers = range(10)
>>> numbers
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] #有这样一个list,想让每个数字增加3,然后输出到一个新的list中
>>> new_numbers = []
>>> for i in numbers:
... new_numbers.append(add(i)) #调用add()函数,并append到list中
...
>>> new_numbers
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
在这个例子中,add()只是一个中间操作。当然,上面的例子完全可以用别的方式实现。比如:
>>> new_numbers = [ i+3 for i in numbers ]
>>> new_numbers
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
首先说明,这种列表解析的方式是非常非常好的。
但是,我们偏偏要用lambda这个函数替代add(x),如果看官和我一样这么偏执,就可以:
>>> lam = lambda x:x+3
>>> n2 = []
>>> for i in numbers:
... n2.append(lam(i))
...
>>> n2
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
这里的lam就相当于add(x),请看官对应一下,这一行lambda x:x+3就完成add(x)的三行(还是两行?),特别是最后返回值。还可以写这样的例子:
>>> g = lambda x,y:x+y #x+y,并返回结果
>>> g(3,4)
7
>>> (lambda x:x**2)(4) #返回4的平方
16
通过上面例子,总结一下lambda函数的使用方法:
- 在lambda后面直接跟变量
- 变量后面是冒号
- 冒号后面是表达式,表达式计算结果就是本函数的返回值
为了简明扼要,用一个式子表示是必要的:
lambda arg1, arg2, ...argN : expression using arguments
要特别提醒看官:虽然lambda 函数可以接收任意多个参数 (包括可选参数) 并且返回单个表达式的值,但是lambda 函数不能包含命令,包含的表达式不能超过一个。不要试图向 lambda 函数中塞入太多的东西;如果你需要更复杂的东西,应该定义一个普通函数,然后想让它多长就多长。
就lambda而言,它并没有给程序带来性能上的提升,它带来的是代码的简洁。比如,要打印一个list,里面依次是某个数字的1次方,二次方,三次方,四次方。用lambda可以这样做:
>>> lamb = [ lambda x:x,lambda x:x**2,lambda x:x**3,lambda x:x**4 ]
>>> for i in lamb:
... print i(3),
...
3 9 27 81
lambda做为一个单行的函数,在编程实践中,可以选择使用。
map
先看一个例子,还是上面讲述lambda的时候第一个例子,用map也能够实现:
>>> numbers
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] #把列表中每一项都加3
>>> map(add,numbers) #add(x)是上面讲述的那个函数,但是这里只引用函数名称即可
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
>>> map(lambda x: x+3,numbers) #用lambda当然可以啦
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
map()是python的一个内置函数,它的基本样式是:
map(func,seq)
func是一个函数,seq是一个序列对象。在执行的时候,序列对象中的每个元素,按照从左到右的顺序,依次被取出来,并塞入到func那个函数里面,并将func的返回值依次存到一个list中。
在应用中,map的所能实现的,也可以用别的方式实现。比如:
>>> items = [1,2,3,4,5]
>>> squared = []
>>> for i in items:
... squared.append(i**2)
...
>>> squared
[1, 4, 9, 16, 25]
>>> def sqr(x): return x**2
...
>>> map(sqr,items)
[1, 4, 9, 16, 25]
>>> map(lambda x: x**2, items)
[1, 4, 9, 16, 25]
>>> [ x**2 for x in items ] #这个我最喜欢了,一般情况下速度足够快,而且可读性强
[1, 4, 9, 16, 25]
条条大路通罗马,以上方法,在编程中,自己根据需要来选用啦。
在以上感性认识的基础上,在来浏览有关map()的官方说明,能够更明白一些。
理解要点:
- 对iterable中的每个元素,依次应用function的方法(函数)(这本质上就是一个for循环)。
- 将所有结果返回一个list。
- 如果参数很多,则对那些参数并行执行function。
例如:
>>> lst1 = [1,2,3,4,5]
>>> lst2 = [6,7,8,9,0]
>>> map(lambda x,y: x+y, lst1,lst2) #将两个列表中的对应项加起来,并返回一个结果列表
[7, 9, 11, 13, 5]
请看官注意了,上面这个例子如果用for循环来写,还不是很难,如果扩展一下,下面的例子用for来改写,就要小心了:
>>> lst1 = [1,2,3,4,5]
>>> lst2 = [6,7,8,9,0]
>>> lst3 = [7,8,9,2,1]
>>> map(lambda x,y,z: x+y+z, lst1,lst2,lst3)
[14, 17, 20, 15, 6]
这才显示出map的简洁优雅。
reduce
直接看这个:
>>> reduce(lambda x,y: x+y,[1,2,3,4,5])
15
请看官仔细观察,是否能够看出是如何运算的呢?画一个图:
还记得map是怎么运算的吗?忘了?看代码:
>>> list1 = [1,2,3,4,5,6,7,8,9]
>>> list2 = [9,8,7,6,5,4,3,2,1]
>>> map(lambda x,y: x+y, list1,list2)
[10, 10, 10, 10, 10, 10, 10, 10, 10]
看官对比一下,就知道两个的区别了。原来map是上下运算,reduce是横着逐个元素进行运算。
权威的解释来自官网:
def reduce(function, iterable, initializer=None):
it = iter(iterable)
if initializer is None:
try:
initializer = next(it)
except StopIteration:
raise TypeError('reduce() of empty sequence with no initial value')
accum_value = initializer
for x in it:
accum_value = function(accum_value, x)
return accum_value
如果用我们熟悉的for循环来做上面reduce的事情,可以这样来做:
>>> lst = range(1,6)
>>> lst
[1, 2, 3, 4, 5]
>>> r = 0
>>> for i in range(len(lst)):
... r += lst[i]
...
>>> r
15
for普世的,reduce是简洁的。
为了锻炼思维,看这么一个问题,有两个list,a = [3,9,8,5,2],b=[1,4,9,2,6],计算:a[0]b[0]+a[1]b[1]+…的结果。
>>> a
[3, 9, 8, 5, 2]
>>> b
[1, 4, 9, 2, 6]
>>> zip(a,b) #复习一下zip,下面的方法中要用到
[(3, 1), (9, 4), (8, 9), (5, 2), (2, 6)]
>>> sum(x*y for x,y in zip(a,b)) #解析后直接求和
133
>>> new_list = [x*y for x,y in zip(a,b)] #可以看做是上面方法的分布实施
>>> #这样解析也可以:new_tuple = (x*y for x,y in zip(a,b))
>>> new_list
[3, 36, 72, 10, 12]
>>> sum(new_list) #或者:sum(new_tuple)
133
>>> reduce(lambda sum,(x,y): sum+x*y,zip(a,b),0) #这个方法是在耍酷呢吗?
133
>>> from operator import add,mul #耍酷的方法也不止一个
>>> reduce(add,map(mul,a,b))
133
>>> reduce(lambda x,y: x+y, map(lambda x,y: x*y, a,b)) #map,reduce,lambda都齐全了,更酷吗?
133
最后,要特别提醒:如果读者使用的是python3,跟上面有点不一样,因为在python3中,reduce()已经从全局命名空间中移除,放到了functools模块中,如果要是用,需要用from functools import reduce
引入之。
filter
filter的中文含义是“过滤器”,在python中,它就是起到了过滤器的作用。首先看官方说明:
这次真的不翻译了(好像以往也没有怎么翻译呀),而且也不解释要点了。请列位务必自己阅读上面的文字,并且理解其含义。英语,无论怎么强调都是不过分的,哪怕是做乞丐,说两句英语,没准还可以讨到英镑美元呢。
通过下面代码体会:
>>> numbers = range(-5,5)
>>> numbers
[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4]
>>> filter(lambda x: x>0, numbers)
[1, 2, 3, 4]
>>> [x for x in numbers if x>0] #与上面那句等效
[1, 2, 3, 4]
>>> filter(lambda c: c!='i', 'qiwsir') #能不能对应上面文档说明那句话呢?
'qwsr' #“If iterable is a string or a tuple, the result also has that type;”
至此,介绍了几个函数,这些函数在对程序的性能提高上,并没有显著或者稳定预期,但是,在代码的简洁上,是有目共睹的。有时候是可以用来秀一秀,彰显python的优雅和自己耍酷。如何用、怎么用,看你自己的喜好了。
转载请注明:www.ainoob.cn » 零基础学Python:函数(4)