函數(shù)(4)

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

遞歸

什么是遞歸？

遞歸，見遞歸.

這是對“遞歸”最精簡的定義。還有故事類型的定義.

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

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

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

最典型的遞歸例子之一是斐波那契數(shù)列，雖然前面用迭代的方式實現(xiàn)了它，但是那種方法在理解上不很直接。如果忘記了這個數(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

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

$ python 20401.py
55

fib(n-1) + fib(n-2)就是又調(diào)用了這個函數(shù)自己，實現(xiàn)遞歸。為了明確遞歸的過程，下面走一個計算過程（考慮到次數(shù)不能太多，就讓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)，在函數(shù)中就要走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. 最后計算第一步中的結(jié)果：fib(3-1) + fib(3-2) = 1 + 1 = 2，將計算結(jié)果2作為返回值

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

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

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

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

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

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

幾個特殊函數(shù)

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

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

編程范型或編程范式（英語：Programming paradigm），（范即模范之意，范式即模式、方法），是一類典型的編程風(fēng)格，是指從事軟件工程的一類典型的風(fēng)格（可以對照方法學(xué)）。如：函數(shù)式編程、程序編程、面向?qū)ο缶幊獭⒅噶钍骄幊痰鹊葹椴煌木幊谭缎汀?/p>

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

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

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

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

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

filter、map、reduce、lambda、yield

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

（注：本節(jié)不對yield進行介紹，請閱讀《生成器》）

lambda

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

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

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

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

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

但是，我們偏偏要用lambda這個函數(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就相當于add(x)，請看官對應(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后面直接跟變量
• 變量后面是冒號
• 冒號后面是表達式，表達式計算結(jié)果就是本函數(shù)的返回值

為了簡明扼要，用一個式子表示是必要的：

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

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

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

map

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

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

>>> map(add,numbers)                #add(x)是上面講述的那個函數(shù)，但是這里只引用函數(shù)名稱即可
[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的一個內(nèi)置函數(shù)，它的基本樣式是：

map(func,seq)

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

在應(yīng)用中，map的所能實現(xiàn)的，也可以用別的方式實現(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 ]     #這個我最喜歡了，一般情況下速度足夠快，而且可讀性強
[1, 4, 9, 16, 25]

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

在以上感性認識的基礎(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.

理解要點：

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

例如：

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

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

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]

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

權(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是簡潔的。

為了鍛煉思維，看這么一個問題，有兩個list，a = [3,9,8,5,2],b=[1,4,9,2,6],計算：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)]    #可以看做是上面方法的分布實施

>>> #這樣解析也可以：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()已經(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.

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

通過下面代碼體會：

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

至此，介紹了幾個函數(shù)，這些函數(shù)在對程序的性能提高上，并沒有顯著或者穩(wěn)定預(yù)期，但是，在代碼的簡潔上，是有目共睹的。有時候是可以用來秀一秀，彰顯python的優(yōu)雅和自己耍酷。如何用、怎么用，看你自己的喜好了。