#函数(4)

还记得在[《迭代》](./128.md)中提到的那几个说出来就让人感觉牛X的名词吗？前面已经学习过“循环”、“遍历”和“迭代”了。现在来看“递归”。

##递归

什么是递归？

这是对“递归”最精简的定义。还有故事类型的定义.

如果用上面的做递归的定义，总感觉有点调侃，来个严肃的(选自维基百科)：

最典型的递归例子之一是斐波那契数列，虽然前面用迭代的方式实现了它，但是那种方法在理解上不很直接。如果忘记了这个数列的定义，可以回到[《练习》](./129.md)中查看。

根据斐波那契数列的定义，可以直接写成这样的斐波那契数列递归函数。

#!/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。

##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的一个内置函数，它的基本样式是：

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的优雅和自己耍酷。如何用、怎么用，看你自己的喜好了。

[总目录](./index.md)   |   [上节：函数(3)](./203.md)   |   [下节：函数练习](./205.md)

如果你认为有必要打赏我，请通过支付宝：**qiwsir@126.com**,不胜感激。