零基础学Python:函数(4)

还记得在《迭代》中提到的那几个说出来就让人感觉牛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)

  1. n=3,fib(3),自然要走return fib(3-1) + fib(3-2)分支
  2. 先看fib(3-1),即fib(2),也要走else分支,于是计算fib(2-1) + fib(2-2)
  3. fib(2-1)即fib(1),在函数中就要走elif分支,返回1,即fib(2-1)=1。同理,容易得到fib(2-2)=0。将这两个值返回到上面一步。得到fib(3-1)=1+0=1
  4. 再计算fib(3-2),就简单了一些,返回的值是1,即fib(3-2)=1
  5. 最后计算第一步中的结果: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的优雅和自己耍酷。如何用、怎么用,看你自己的喜好了。