函數(shù)(4)

還記得在《迭代》中提到的那幾個(gè)說出來就讓人感覺牛X的名詞嗎？前面已經(jīng)學(xué)習(xí)過“循環(huán)”、“遍歷”和“迭代”了?，F(xiàn)在來看“遞歸”。

遞歸

什么是遞歸？

遞歸，見遞歸.

這是對(duì)“遞歸”最精簡(jiǎn)的定義。還有故事類型的定義.

從前有座山，山里有座廟，廟里有個(gè)老和尚，正在給小和尚講故事。故事是什么呢？“從前有座山，山里有座廟，廟里有個(gè)老和尚，正在給小和尚講故事。故事是什么呢？“從前有座山，山里有座廟，廟里有個(gè)老和尚，正在給小和尚講故事。故事是什么呢？……””

如果用上面的做遞歸的定義，總感覺有點(diǎn)調(diào)侃，來個(gè)嚴(yán)肅的(選自維基百科)：

遞歸（英語：Recursion），又譯為遞回，在數(shù)學(xué)與計(jì)算機(jī)科學(xué)中，是指在函數(shù)的定義中使用函數(shù)自身的方法。

最典型的遞歸例子之一是斐波那契數(shù)列，雖然前面用迭代的方式實(shí)現(xiàn)了它，但是那種方法在理解上不很直接。如果忘記了這個(gè)數(shù)列的定義，可以回到《練習(xí)》中查看。

根據(jù)斐波那契數(shù)列的定義，可以直接寫成這樣的斐波那契數(shù)列遞歸函數(shù)。

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

把上述代碼保存。這個(gè)代碼的意圖是要得到n=10的值。運(yùn)行之：

$ python 20401.py
55

fib(n-1) + fib(n-2)就是又調(diào)用了這個(gè)函數(shù)自己，實(shí)現(xiàn)遞歸。為了明確遞歸的過程，下面走一個(gè)計(jì)算過程（考慮到次數(shù)不能太多，就讓n=3）

1. n=3,fib(3)，自然要走return fib(3-1) + fib(3-2)分支
2. 先看fib(3-1),即fib(2)，也要走else分支，于是計(jì)算fib(2-1) + fib(2-2)
3. fib(2-1)即fib(1)，在函數(shù)中就要走elif分支，返回1，即fib(2-1)=1。同理，容易得到fib(2-2)=0。將這兩個(gè)值返回到上面一步。得到fib(3-1)=1+0=1
4. 再計(jì)算fib(3-2),就簡(jiǎn)單了一些，返回的值是1，即fib(3-2)=1
5. 最后計(jì)算第一步中的結(jié)果：fib(3-1) + fib(3-2) = 1 + 1 = 2，將計(jì)算結(jié)果2作為返回值

從而得到fib(3)的結(jié)果是2。

從上面的過程中可以看出，每個(gè)遞歸的過程，都是向著最初的已知條件a0=0,a1=1方向挺近一步，直到通過這個(gè)最底層的條件得到結(jié)果，然后再一層一層向上回饋計(jì)算機(jī)結(jié)果。

其實(shí)，上面的代碼有一個(gè)問題。因?yàn)?code>a0=0,a1=1是已知的了，不需要每次都判斷一邊。所以，還可以優(yōu)化一下。優(yōu)化的基本方案就是初始化最初的兩個(gè)值。

#!/usr/bin/env python
# coding=utf-8

"""
the better Fibonacci
"""
meno = {0:0, 1:1}    #初始化

def fib(n):
    if not n in meno:    #如果不在初始化范圍內(nèi)
        meno[n] = fib(n-1) + fib(n-2)
    return meno[n]

if __name__ == "__main__":
    f = fib(10)
    print f

#運(yùn)行結(jié)果
$ python 20402.py 
55

以上實(shí)現(xiàn)了遞歸，但是，至少在python中，遞歸要慎重使用。在一般情況下，遞歸是能夠被迭代或者循環(huán)替代的，而且后者的效率常常比遞歸要高。所以，我個(gè)人的建議是，對(duì)使用遞歸要考慮的周密一下，不小心就永遠(yuǎn)運(yùn)行下去了。

幾個(gè)特殊函數(shù)

前面已經(jīng)知道了如何編寫、調(diào)用函數(shù)。此外，在python中，有幾個(gè)特別的函數(shù)，很有意思，它們常常被看做是python能夠進(jìn)行所謂“函數(shù)式編程”的見證。

如果以前沒有聽過，等你開始進(jìn)入編程界，也會(huì)經(jīng)常聽人說“函數(shù)式編程”、“面向?qū)ο缶幊獭薄ⅰ爸噶钍骄幊獭钡葘儆?。它們是什么呢？這個(gè)話題要從“編程范式”講起。（以下內(nèi)容源自維基百科）

編程范型或編程范式（英語：Programming paradigm），（范即模范之意，范式即模式、方法），是一類典型的編程風(fēng)格，是指從事軟件工程的一類典型的風(fēng)格（可以對(duì)照方法學(xué)）。如：函數(shù)式編程、程序編程、面向?qū)ο缶幊?、指令式編程等等為不同的編程范型?/p>

編程范型提供了（同時(shí)決定了）程序員對(duì)程序執(zhí)行的看法。例如，在面向?qū)ο缶幊讨?，程序員認(rèn)為程序是一系列相互作用的對(duì)象，而在函數(shù)式編程中一個(gè)程序會(huì)被看作是一個(gè)無狀態(tài)的函數(shù)計(jì)算的串行。

正如軟件工程中不同的群體會(huì)提倡不同的“方法學(xué)”一樣，不同的編程語言也會(huì)提倡不同的“編程范型”。一些語言是專門為某個(gè)特定的范型設(shè)計(jì)的（如Smalltalk和Java支持面向?qū)ο缶幊蹋鳫askell和Scheme則支持函數(shù)式編程），同時(shí)還有另一些語言支持多種范型（如Ruby、Common Lisp、Python和Oz）。

編程范型和編程語言之間的關(guān)系可能十分復(fù)雜，由于一個(gè)編程語言可以支持多種范型。例如，C++設(shè)計(jì)時(shí)，支持過程化編程、面向?qū)ο缶幊桃约胺盒途幊獭Ｈ欢?，設(shè)計(jì)師和程序員們要考慮如何使用這些范型元素來構(gòu)建一個(gè)程序。一個(gè)人可以用C++寫出一個(gè)完全過程化的程序，另一個(gè)人也可以用C++寫出一個(gè)純粹的面向?qū)ο蟪绦?，甚至還有人可以寫出雜揉了兩種范型的程序。

不管讀者是初學(xué)還是老油條，都建議將上面這段話認(rèn)真讀完，不管理解還是不理解，總能有點(diǎn)感覺的。

正如前面引文中所說的，python是支持多種范型的語言，可以進(jìn)行所謂函數(shù)式編程，其突出體現(xiàn)在有這么幾個(gè)函數(shù)：

filter、map、reduce、lambda、yield

有了它們，最大的好處是程序更簡(jiǎn)潔；沒有它們，程序也可以用別的方式實(shí)現(xiàn)，只不過麻煩一些罷了。所以，還是能用則用之吧。更何況，恰當(dāng)?shù)厥褂眠@幾個(gè)函數(shù)，能讓別人感覺你更牛X。

（注：本節(jié)不對(duì)yield進(jìn)行介紹，請(qǐng)閱讀《生成器》）

lambda

lambda函數(shù)，是一個(gè)只用一行就能解決問題的函數(shù)，聽著是多么誘人呀?？聪旅娴睦樱?/p>

>>> def add(x):     #定義一個(gè)函數(shù)，將輸入的變量增加3,然后返回增加之后的值
...     x += 3
...     return x
... 
>>> numbers = range(10)
>>> numbers
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]  #有這樣一個(gè)list，想讓每個(gè)數(shù)字增加3,然后輸出到一個(gè)新的list中

>>> new_numbers = []
>>> for i in numbers:
...     new_numbers.append(add(i))  #調(diào)用add()函數(shù)，并append到list中
... 
>>> new_numbers
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

在這個(gè)例子中，add()只是一個(gè)中間操作。當(dāng)然，上面的例子完全可以用別的方式實(shí)現(xiàn)。比如：

>>> new_numbers = [ i+3 for i in numbers ]
>>> new_numbers
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

首先說明，這種列表解析的方式是非常非常好的。

但是，我們偏偏要用lambda這個(gè)函數(shù)替代add(x)，如果看官和我一樣這么偏執(zhí)，就可以：

>>> 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就相當(dāng)于add(x)，請(qǐng)看官對(duì)應(yīng)一下，這一行l(wèi)ambda x:x+3就完成add(x)的三行（還是兩行？），特別是最后返回值。還可以寫這樣的例子：

>>> g = lambda x,y:x+y  #x+y,并返回結(jié)果
>>> g(3,4)
7
>>> (lambda x:x**2)(4)  #返回4的平方
16

通過上面例子，總結(jié)一下lambda函數(shù)的使用方法：

• 在lambda后面直接跟變量
• 變量后面是冒號(hào)
• 冒號(hào)后面是表達(dá)式，表達(dá)式計(jì)算結(jié)果就是本函數(shù)的返回值

為了簡(jiǎn)明扼要，用一個(gè)式子表示是必要的：

lambda arg1, arg2, ...argN : expression using arguments

要特別提醒看官：雖然lambda 函數(shù)可以接收任意多個(gè)參數(shù) (包括可選參數(shù)) 并且返回單個(gè)表達(dá)式的值，但是lambda 函數(shù)不能包含命令，包含的表達(dá)式不能超過一個(gè)。不要試圖向 lambda 函數(shù)中塞入太多的東西；如果你需要更復(fù)雜的東西，應(yīng)該定義一個(gè)普通函數(shù)，然后想讓它多長就多長。

就lambda而言，它并沒有給程序帶來性能上的提升，它帶來的是代碼的簡(jiǎn)潔。比如，要打印一個(gè)list，里面依次是某個(gè)數(shù)字的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做為一個(gè)單行的函數(shù)，在編程實(shí)踐中，可以選擇使用。

map

先看一個(gè)例子，還是上面講述lambda的時(shí)候第一個(gè)例子，用map也能夠?qū)崿F(xiàn)：

>>> numbers
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]      #把列表中每一項(xiàng)都加3

>>> map(add,numbers)                #add(x)是上面講述的那個(gè)函數(shù)，但是這里只引用函數(shù)名稱即可
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

>>> map(lambda x: x+3,numbers)      #用lambda當(dāng)然可以啦
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

map()是python的一個(gè)內(nèi)置函數(shù)，它的基本樣式是：

map(func,seq)

func是一個(gè)函數(shù)，seq是一個(gè)序列對(duì)象。在執(zhí)行的時(shí)候，序列對(duì)象中的每個(gè)元素，按照從左到右的順序，依次被取出來，并塞入到func那個(gè)函數(shù)里面，并將func的返回值依次存到一個(gè)list中。

在應(yīng)用中，map的所能實(shí)現(xiàn)的，也可以用別的方式實(shí)現(xiàn)。比如：

>>> 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 ]     #這個(gè)我最喜歡了，一般情況下速度足夠快，而且可讀性強(qiáng)
[1, 4, 9, 16, 25]

條條大路通羅馬，以上方法，在編程中，自己根據(jù)需要來選用啦。

在以上感性認(rèn)識(shí)的基礎(chǔ)上，在來瀏覽有關(guān)map()的官方說明，能夠更明白一些。

map(function, iterable, ...)

Apply function to every item of iterable and return a list of the results. If additional iterable arguments are passed, function must take that many arguments and is applied to the items from all iterables in parallel. If one iterable is shorter than another it is assumed to be extended with None items. If function is None, the identity function is assumed; if there are multiple arguments, map() returns a list consisting of tuples containing the corresponding items from all iterables (a kind of transpose operation). The iterable arguments may be a sequence or any iterable object; the result is always a list.

理解要點(diǎn)：

• 對(duì)iterable中的每個(gè)元素，依次應(yīng)用function的方法（函數(shù)）（這本質(zhì)上就是一個(gè)for循環(huán)）。
• 將所有結(jié)果返回一個(gè)list。
• 如果參數(shù)很多，則對(duì)那些參數(shù)并行執(zhí)行function。

例如：

>>> lst1 = [1,2,3,4,5]
>>> lst2 = [6,7,8,9,0]
>>> map(lambda x,y: x+y, lst1,lst2)     #將兩個(gè)列表中的對(duì)應(yīng)項(xiàng)加起來，并返回一個(gè)結(jié)果列表
[7, 9, 11, 13, 5]

請(qǐng)看官注意了，上面這個(gè)例子如果用for循環(huán)來寫，還不是很難，如果擴(kuò)展一下，下面的例子用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的簡(jiǎn)潔優(yōu)雅。

reduce

直接看這個(gè)：

>>> reduce(lambda x,y: x+y,[1,2,3,4,5])
15

請(qǐng)看官仔細(xì)觀察，是否能夠看出是如何運(yùn)算的呢？畫一個(gè)圖：

還記得map是怎么運(yùn)算的嗎？忘了？看代碼：

>>> 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]

看官對(duì)比一下，就知道兩個(gè)的區(qū)別了。原來map是上下運(yùn)算，reduce是橫著逐個(gè)元素進(jìn)行運(yùn)算。

權(quán)威的解釋來自官網(wǎng)：

reduce(function, iterable[, initializer])

Apply function of two arguments cumulatively to the items of iterable, from left to right, so as to reduce the iterable to a single value. For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates ((((1+2)+3)+4)+5). The left argument, x, is the accumulated value and the right argument, y, is the update value from the iterable. If the optional initializer is present, it is placed before the items of the iterable in the calculation, and serves as a default when the iterable is empty. If initializer is not given and iterable contains only one item, the first item is returned. Roughly equivalent to:

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循環(huán)來做上面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是簡(jiǎn)潔的。

為了鍛煉思維，看這么一個(gè)問題，有兩個(gè)list，a = [3,9,8,5,2],b=[1,4,9,2,6],計(jì)算：a[0]b[0]+a[1]b[1]+...的結(jié)果。

>>> a
[3, 9, 8, 5, 2]
>>> b
[1, 4, 9, 2, 6]

>>> zip(a,b)        #復(fù)習(xí)一下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)]    #可以看做是上面方法的分布實(shí)施

>>> #這樣解析也可以：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)    #這個(gè)方法是在耍酷呢嗎？
133

>>> from operator import add,mul            #?？岬姆椒ㄒ膊恢挂粋€(gè)
>>> 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，跟上面有點(diǎn)不一樣，因?yàn)樵趐ython3中，reduce()已經(jīng)從全局命名空間中移除，放到了functools模塊中，如果要是用，需要用from functools import reduce引入之。

filter

filter的中文含義是“過濾器”，在python中，它就是起到了過濾器的作用。首先看官方說明：

filter(function, iterable)

Construct a list from those elements of iterable for which function returns true. iterable may be either a sequence, a container which supports iteration, or an iterator. If iterable is a string or a tuple, the result also has that type; otherwise it is always a list. If function is None, the identity function is assumed, that is, all elements of iterable that are false are removed.

Note that filter(function, iterable) is equivalent to [item for item in iterable if function(item)] if function is not None and [item for item in iterable if item] if function is None.

這次真的不翻譯了（好像以往也沒有怎么翻譯呀），而且也不解釋要點(diǎn)了。請(qǐng)列位務(wù)必自己閱讀上面的文字，并且理解其含義。英語，無論怎么強(qiáng)調(diào)都是不過分的，哪怕是做乞丐，說兩句英語，沒準(zhǔn)還可以討到英鎊美元呢。

通過下面代碼體會(huì)：

>>> 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')  #能不能對(duì)應(yīng)上面文檔說明那句話呢？
'qwsr'                                  #“If iterable is a string or a tuple, the result also has that type;”

至此，介紹了幾個(gè)函數(shù)，這些函數(shù)在對(duì)程序的性能提高上，并沒有顯著或者穩(wěn)定預(yù)期，但是，在代碼的簡(jiǎn)潔上，是有目共睹的。有時(shí)候是可以用來秀一秀，彰顯python的優(yōu)雅和自己?？帷Ｈ绾斡谩⒃趺从?，看你自己的喜好了。