Python 函數(shù)的執(zhí)行流程-函數(shù)遞歸-匿名函數(shù)-生成器

1 函數(shù)的執(zhí)行流程

函數(shù)的執(zhí)行需要對(duì)函數(shù)進(jìn)行壓棧的，什么是壓棧呢，簡而言之就是在函數(shù)執(zhí)行時(shí)在棧中創(chuàng)建棧幀存放需要變量以及指針的意思。具體涉及的知識(shí)非常多，這里就已一個(gè)Python腳本簡單進(jìn)行分析。

當(dāng)我們運(yùn)行上面代碼時(shí)，它的執(zhí)行流程如下：

全局棧幀中生成foo1、foo2、foo3、main函數(shù)對(duì)象

main函數(shù)調(diào)用

main中查找內(nèi)建函數(shù)print壓棧，將常量字符串壓棧，調(diào)用函數(shù)，彈出棧頂

main中全局查找函數(shù)foo1壓棧，將常量100、101壓棧，調(diào)用函數(shù)foo1，創(chuàng)建棧幀。print函數(shù)壓棧，字符串和變量b、b1壓棧，調(diào)用函數(shù)，彈出棧頂，返回值。

main中全局查找foo2函數(shù)壓棧，將常量200壓棧，調(diào)用foo2，創(chuàng)建棧幀。foo3函數(shù)壓棧，變量c引用壓棧，調(diào)用foo3，創(chuàng)建棧幀。foo3完成print函數(shù)調(diào)用返回。foo2恢復(fù)調(diào)用，執(zhí)行print語句后，返回值。main中foo2調(diào)用結(jié)束后彈出棧頂，main繼續(xù)執(zhí)行print函數(shù)調(diào)用，彈出棧頂，main函數(shù)返回

1.1 字節(jié)碼了解壓棧過程

Python 代碼先被編譯為字節(jié)碼后，再由Python虛擬機(jī)來執(zhí)行字節(jié)碼， Python的字節(jié)碼是一種類似匯編指令的中間語言， 一個(gè)Python語句會(huì)對(duì)應(yīng)若干字節(jié)碼指令，虛擬機(jī)一條一條執(zhí)行字節(jié)碼指令， 從而完成程序執(zhí)行。Python?dis 模塊支持對(duì)Python代碼進(jìn)行反匯編， 生成字節(jié)碼指令。下面針對(duì)上面的例子通過字節(jié)碼理解函數(shù)調(diào)用時(shí)的過程。

字節(jié)碼含義：

LOAD_GLOBAL：加載全局函數(shù)(print)

LOAD_CONST: 加載常量

CALL_FUNCTION: 函數(shù)調(diào)用

POP_TOP：彈出棧頂

RETURN_VALUE： 返回值

1.2 嵌套函數(shù)的壓棧

函數(shù)只有在執(zhí)行的時(shí)候才會(huì)壓棧，所以在outer執(zhí)行時(shí)，會(huì)開辟?？臻g壓棧(c,inner)

執(zhí)行完后，刪除?？臻g，但是由于outer返回了內(nèi)部函數(shù)inner，但并沒有執(zhí)行，所以不會(huì)繼續(xù)壓棧，當(dāng)執(zhí)行a的時(shí)候，會(huì)重新壓棧，而此時(shí)內(nèi)部函數(shù)已經(jīng)記住了外部自由變量c，并且每次調(diào)用outer都會(huì)重新生成一個(gè)inner。

注意：這種情況叫做閉包，自由變量c會(huì)被當(dāng)成內(nèi)部函數(shù)inner的一個(gè)屬性，被調(diào)用。

PS：內(nèi)存兩大區(qū)域(棧，堆)。垃圾回收，清理的是堆中的空間。函數(shù)的調(diào)用就是壓棧的過程，而變量的創(chuàng)建都是在堆中完成的。 棧中存儲(chǔ)的都是堆中的內(nèi)存地址的指向，棧清空，并不會(huì)使堆中的對(duì)象被清除，只是指向已經(jīng)被刪除。函數(shù)，變量都是在堆內(nèi)創(chuàng)建的，函數(shù)調(diào)用需要壓棧

2 遞歸

函數(shù)直接或者間接的調(diào)用自身就叫遞歸，遞歸需要有邊界條件、遞歸前進(jìn)段、遞歸返回段，當(dāng)邊界條件不滿足的時(shí)候，遞歸前進(jìn)，當(dāng)邊界條件滿足時(shí)，遞歸返回。注意：遞歸一定要有邊界條件，否則可能會(huì)造成內(nèi)存溢出。

2.1 遞歸函數(shù)

前面我們學(xué)過斐波那契序列，利用遞歸函數(shù)，我們可以更簡潔的編寫一個(gè)計(jì)算斐波那契序列第N項(xiàng)，或者前N項(xiàng)的代碼：

在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞推的方法定義：F(1)=1，F(xiàn)(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）

很多人可能不明白其中原理，這里簡要說明一下,以fib(6)為例子:

fib(6) 返回 fib(5) + fib(4)

fib(5) 返回 fib(4) + fib(3)

fib(4) 返回 fib(3) + fib(2)

fib(3) 返回 fib(2) + fib(1)

fib(2),fib(1) 是邊界，return 1，然后逐級(jí)調(diào)用返回

遞歸的要求：

遞歸一定要有退出條件，遞歸調(diào)用一定要執(zhí)行到這個(gè)退出條件。沒有退出條件的遞歸調(diào)用，就是無限調(diào)用

遞歸調(diào)用的深度不宜過深,Python對(duì)遞歸的深度做了限制，以保護(hù)解釋器，超過遞歸深度限制，則拋出RecursionError異常。

使用sys.getrecursionlimit()獲取當(dāng)前解釋器限制的最大遞歸深度

2.2 遞歸的性能

由于Python是預(yù)先計(jì)算等式右邊的，所以我們發(fā)現(xiàn)，上圖中，重復(fù)計(jì)算了fib(4)和fib(3)那么效率呢？由于只是計(jì)算了fib(6)，如果fib(35)呢？可以預(yù)想，它要重復(fù)計(jì)算多少次啊。這里我們來測(cè)試一下它執(zhí)行的時(shí)間。

經(jīng)過對(duì)比，我們發(fā)現(xiàn)使用遞歸雖然代碼更優(yōu)美了，但是運(yùn)行時(shí)間還不如我們的普通循環(huán)的版本，這是因?yàn)檫f歸重復(fù)計(jì)算了很多次，當(dāng)規(guī)模到達(dá)一定程度時(shí)，那么這個(gè)時(shí)間是成指數(shù)遞增的的。

總結(jié)一下現(xiàn)在的問題：

循環(huán)稍微復(fù)雜一點(diǎn)，但是只要不是死循環(huán)，可以多次迭代直至算出結(jié)果

fib函數(shù)代碼極簡易懂，但是只要獲取到最外層的函數(shù)調(diào)用，內(nèi)部跌過結(jié)果都是中間結(jié)果。而且給定一個(gè)n都要進(jìn)行近2n次遞歸，深度越深，效率越低。為了獲取斐波那契數(shù)量需要在外面套一個(gè)n次的循環(huán)，效率就更低了。

遞歸還有深度限制，如果遞歸復(fù)雜，函數(shù)反復(fù)壓棧，棧內(nèi)存就很快溢出了。

2.3 遞歸的優(yōu)化

?如何優(yōu)化呢？前面的版本使用遞歸函數(shù)時(shí)會(huì)重復(fù)計(jì)算一些相同的數(shù)據(jù)，那么我們來改進(jìn)一下，在代碼層面對(duì)遞歸的特性進(jìn)行優(yōu)化。

代碼優(yōu)化后，發(fā)現(xiàn)運(yùn)行時(shí)間很快，因?yàn)橛?jì)算的是fib(n),fib(n-1)..fib(1)并沒有進(jìn)行重復(fù)計(jì)算，所以要使用遞歸，必須要考慮重復(fù)計(jì)算以及函數(shù)遞歸調(diào)用時(shí)產(chǎn)生的內(nèi)存浪費(fèi)等。

2.4 間接遞歸

間接遞歸，就是通過別的函數(shù)，來調(diào)用函數(shù)本身，下面來看一個(gè)例子，來理解間接遞歸的概念：

我們可以看到，這種遞歸調(diào)用是非常危險(xiǎn)的，但是往往這種情況在代碼復(fù)雜的情況下，還是可能發(fā)生這種調(diào)用。要用代碼規(guī)范來避免這種遞歸調(diào)用的發(fā)生。

2.5 遞歸總結(jié)

遞歸是一種很自然的表達(dá)，符合邏輯思維：

運(yùn)行效率低，每一次調(diào)用函數(shù)都要開辟棧幀。

有深度限制，如果遞歸層次太深，函數(shù)反復(fù)壓棧，棧內(nèi)存很快就溢出了。

如果是有限次數(shù)的遞歸，可以使用遞歸調(diào)用，或者使用循環(huán)代替，雖然代碼稍微復(fù)雜一點(diǎn)，但是只要不是死循環(huán)，可以多次疊代直至算出結(jié)果。

絕大多數(shù)遞歸，都可以使用循環(huán)實(shí)現(xiàn)，能不用遞歸則不用遞歸。

3 匿名函數(shù)

沒有名字的函數(shù)，在Python中被稱為匿名函數(shù)，考慮一下，我們之前都是通過def語句定義函數(shù)的名字開始定義一個(gè)函數(shù)的，那么沒有名字改如何定義?沒有名字該如何調(diào)用呢？

Python中借助lambda表達(dá)式構(gòu)建匿名函數(shù)。它的格式為：

需要注意的是：

冒號(hào)左邊是參數(shù)裂變，但不要括號(hào)。

冒號(hào)右邊是函數(shù)體，但不能出現(xiàn)等號(hào)。

函數(shù)體只能寫一行，不能使用分號(hào)分隔多個(gè)語句。(也被稱為單行函數(shù))

return語句，不寫return關(guān)鍵字

下面來看一下各種匿名函數(shù)的寫法

lambda是一匿名函數(shù)，我們?cè)谒竺婕永ㄌ?hào)就表示函數(shù)調(diào)用

在高階函數(shù)傳參時(shí)，使用lambda表達(dá)式，往往能簡化代碼

還記得，我們之前的默認(rèn)值字典嗎，這里的：d = defaultdict(lambda :0)，其實(shí)就等于(lambda :0)()，即當(dāng)我們傳入任意值時(shí)都返回0

4 Python生成器

生成器指的生成器對(duì)象，可以由生成器表達(dá)式得到，也可以使用yield關(guān)鍵字得到一個(gè)生成器函數(shù)，調(diào)用這個(gè)函數(shù)返回一個(gè)生成器對(duì)象。

生成器函數(shù)，函數(shù)體中包含yield關(guān)鍵字的函數(shù)，就是生成器函數(shù)，調(diào)用后返回生成器對(duì)象。關(guān)于生成器對(duì)象，我們可以理解它就是一個(gè)可迭代對(duì)象，是一個(gè)迭代器，只不過它是延遲計(jì)算的，惰性求值的。

4.1 基本結(jié)構(gòu)

我們說在函數(shù)中使用yield關(guān)鍵字來返回?cái)?shù)據(jù)的函數(shù)，叫做生成器函數(shù)，那么我們來寫一個(gè)生成器函數(shù)，看看和return函數(shù)有什么區(qū)別

這個(gè)報(bào)錯(cuò)看起來是不是很熟悉？沒錯(cuò)，和生成器表達(dá)式的結(jié)果是相同的，只不過生成器函數(shù)可以寫的更加的復(fù)雜，現(xiàn)在我們來看下生成器函數(shù)的執(zhí)行過程。

當(dāng)函數(shù)執(zhí)行過程中遇到y(tǒng)ield函數(shù)時(shí)，會(huì)暫停，并把yield表達(dá)式的值返回。

再次執(zhí)行時(shí)會(huì)執(zhí)行到下一個(gè)yield語句

yield關(guān)鍵字``，和return關(guān)鍵字在生成器場(chǎng)景下，不能一起使用。因?yàn)閞eturn語句會(huì)導(dǎo)致當(dāng)前函數(shù)立即返回，無法繼續(xù)執(zhí)行，也無法繼續(xù)獲取下一個(gè)值，并且return語句的返回值也不能被獲取到，還會(huì)產(chǎn)生StopIteration的異常.

再來總結(jié)一下生成器的特點(diǎn)：

包含yield語句的生成器函數(shù)調(diào)用生成生成器對(duì)象的時(shí)候，生成器函數(shù)的函數(shù)體不會(huì)立即執(zhí)行。

next(genreator) 會(huì)從函數(shù)的當(dāng)前位置向后執(zhí)行到之后碰到的一個(gè)yield語句，會(huì)彈出值，并暫停函數(shù)執(zhí)行。

再次調(diào)用next函數(shù)，和上一條一樣的處理結(jié)果

繼續(xù)調(diào)用哪個(gè)next函數(shù)，生成器函數(shù)如果結(jié)束執(zhí)行了（顯示或隱式調(diào)用了return語句），會(huì)拋出StopIteration異常

4.2 使用場(chǎng)景

我們想要生成一個(gè)無限自然數(shù)的序列時(shí)，生成器就是一個(gè)很好的方式

又或者前面的斐波那契序列，我們也可以利用生成器的特點(diǎn)，惰性計(jì)算。

或者包含所有斐波那契序列的生成器

4.3 協(xié)程coriutine

協(xié)程是生成器的一種高級(jí)方法，比進(jìn)程、線程更輕量級(jí)，是在用戶空間調(diào)度函數(shù)的一種實(shí)現(xiàn)，Python 3 的asyncio就是協(xié)程實(shí)現(xiàn)，已經(jīng)加入到了標(biāo)準(zhǔn)庫中，Python 3.5 使用async、await關(guān)鍵字直接原生支持寫成。協(xié)程在現(xiàn)階段來說比較復(fù)雜，后面會(huì)詳細(xì)進(jìn)行說明，這里提一下實(shí)現(xiàn)思路：

有兩個(gè)生成器A、B

next(A)后，A執(zhí)行到了yield語句后暫停，然后去執(zhí)行next(B),B執(zhí)行到y(tǒng)ield語句也暫停，然后再次調(diào)用next(A)，再次調(diào)用next(B)

周而復(fù)始，就實(shí)現(xiàn)了調(diào)度的效果

還可以引入調(diào)度的策略來實(shí)現(xiàn)切換的方式

協(xié)程是一種非搶占式調(diào)度

4.4 yield from

在Python 3.3以后，出現(xiàn)了yield from語法糖。它的用法是

yield from 后面需要一個(gè)可迭代對(duì)象

yield from iterable?實(shí)際上等同于?for item in iterable: yield item

當(dāng)然yield from也可以結(jié)合生成器來使用，因?yàn)樯善饕彩且粋€(gè)可迭代對(duì)象啊。

生成器包生成器，真的是有夠懶的了！