Python 函數的執行流程-函數遞歸-匿名函數-生成器

1 函數的執行流程

函數的執行需要對函數進行壓棧的，什么是壓棧呢，簡而言之就是在函數執行時在棧中創建棧幀存放需要變量以及指針的意思。具體涉及的知識非常多，這里就已一個Python腳本簡單進行分析。

當我們運行上面代碼時，它的執行流程如下：

全局棧幀中生成foo1、foo2、foo3、main函數對象

main函數調用

main中查找內建函數print壓棧，將常量字符串壓棧，調用函數，彈出棧頂

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

main中全局查找foo2函數壓棧，將常量200壓棧，調用foo2，創建棧幀。foo3函數壓棧，變量c引用壓棧，調用foo3，創建棧幀。foo3完成print函數調用返回。foo2恢復調用，執行print語句后，返回值。main中foo2調用結束后彈出棧頂，main繼續執行print函數調用，彈出棧頂，main函數返回

1.1 字節碼了解壓棧過程

Python 代碼先被編譯為字節碼后，再由Python虛擬機來執行字節碼， Python的字節碼是一種類似匯編指令的中間語言， 一個Python語句會對應若干字節碼指令，虛擬機一條一條執行字節碼指令， 從而完成程序執行。Python?dis 模塊支持對Python代碼進行反匯編， 生成字節碼指令。下面針對上面的例子通過字節碼理解函數調用時的過程。

字節碼含義：

LOAD_GLOBAL：加載全局函數(print)

LOAD_CONST: 加載常量

CALL_FUNCTION: 函數調用

POP_TOP：彈出棧頂

RETURN_VALUE： 返回值

1.2 嵌套函數的壓棧

函數只有在執行的時候才會壓棧，所以在outer執行時，會開辟棧空間壓棧(c,inner)

執行完后，刪除棧空間，但是由于outer返回了內部函數inner，但并沒有執行，所以不會繼續壓棧，當執行a的時候，會重新壓棧，而此時內部函數已經記住了外部自由變量c，并且每次調用outer都會重新生成一個inner。

注意：這種情況叫做閉包，自由變量c會被當成內部函數inner的一個屬性，被調用。

PS：內存兩大區域(棧，堆)。垃圾回收，清理的是堆中的空間。函數的調用就是壓棧的過程，而變量的創建都是在堆中完成的。 棧中存儲的都是堆中的內存地址的指向，棧清空，并不會使堆中的對象被清除，只是指向已經被刪除。函數，變量都是在堆內創建的，函數調用需要壓棧

2 遞歸

函數直接或者間接的調用自身就叫遞歸，遞歸需要有邊界條件、遞歸前進段、遞歸返回段，當邊界條件不滿足的時候，遞歸前進，當邊界條件滿足時，遞歸返回。注意：遞歸一定要有邊界條件，否則可能會造成內存溢出。

2.1 遞歸函數

前面我們學過斐波那契序列，利用遞歸函數，我們可以更簡潔的編寫一個計算斐波那契序列第N項，或者前N項的代碼：

在數學上，斐波納契數列以如下被以遞推的方法定義：F(1)=1，F(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，然后逐級調用返回

遞歸的要求：

遞歸一定要有退出條件，遞歸調用一定要執行到這個退出條件。沒有退出條件的遞歸調用，就是無限調用

遞歸調用的深度不宜過深,Python對遞歸的深度做了限制，以保護解釋器，超過遞歸深度限制，則拋出RecursionError異常。

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

2.2 遞歸的性能

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

經過對比，我們發現使用遞歸雖然代碼更優美了，但是運行時間還不如我們的普通循環的版本，這是因為遞歸重復計算了很多次，當規模到達一定程度時，那么這個時間是成指數遞增的的。

總結一下現在的問題：

循環稍微復雜一點，但是只要不是死循環，可以多次迭代直至算出結果

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

遞歸還有深度限制，如果遞歸復雜，函數反復壓棧，棧內存就很快溢出了。

2.3 遞歸的優化

?如何優化呢？前面的版本使用遞歸函數時會重復計算一些相同的數據，那么我們來改進一下，在代碼層面對遞歸的特性進行優化。

代碼優化后，發現運行時間很快，因為計算的是fib(n),fib(n-1)..fib(1)并沒有進行重復計算，所以要使用遞歸，必須要考慮重復計算以及函數遞歸調用時產生的內存浪費等。

2.4 間接遞歸

間接遞歸，就是通過別的函數，來調用函數本身，下面來看一個例子，來理解間接遞歸的概念：

我們可以看到，這種遞歸調用是非常危險的，但是往往這種情況在代碼復雜的情況下，還是可能發生這種調用。要用代碼規范來避免這種遞歸調用的發生。

2.5 遞歸總結

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

運行效率低，每一次調用函數都要開辟棧幀。

有深度限制，如果遞歸層次太深，函數反復壓棧，棧內存很快就溢出了。

如果是有限次數的遞歸，可以使用遞歸調用，或者使用循環代替，雖然代碼稍微復雜一點，但是只要不是死循環，可以多次疊代直至算出結果。

絕大多數遞歸，都可以使用循環實現，能不用遞歸則不用遞歸。

3 匿名函數

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

Python中借助lambda表達式構建匿名函數。它的格式為：

需要注意的是：

冒號左邊是參數裂變，但不要括號。

冒號右邊是函數體，但不能出現等號。

函數體只能寫一行，不能使用分號分隔多個語句。(也被稱為單行函數)

return語句，不寫return關鍵字

下面來看一下各種匿名函數的寫法

lambda是一匿名函數，我們在它后面加括號就表示函數調用

在高階函數傳參時，使用lambda表達式，往往能簡化代碼

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

4 Python生成器

生成器指的生成器對象，可以由生成器表達式得到，也可以使用yield關鍵字得到一個生成器函數，調用這個函數返回一個生成器對象。

生成器函數，函數體中包含yield關鍵字的函數，就是生成器函數，調用后返回生成器對象。關于生成器對象，我們可以理解它就是一個可迭代對象，是一個迭代器，只不過它是延遲計算的，惰性求值的。

4.1 基本結構

我們說在函數中使用yield關鍵字來返回數據的函數，叫做生成器函數，那么我們來寫一個生成器函數，看看和return函數有什么區別

這個報錯看起來是不是很熟悉？沒錯，和生成器表達式的結果是相同的，只不過生成器函數可以寫的更加的復雜，現在我們來看下生成器函數的執行過程。

當函數執行過程中遇到yield函數時，會暫停，并把yield表達式的值返回。

再次執行時會執行到下一個yield語句

yield關鍵字``，和return關鍵字在生成器場景下，不能一起使用。因為return語句會導致當前函數立即返回，無法繼續執行，也無法繼續獲取下一個值，并且return語句的返回值也不能被獲取到，還會產生StopIteration的異常.

再來總結一下生成器的特點：

包含yield語句的生成器函數調用生成生成器對象的時候，生成器函數的函數體不會立即執行。

next(genreator) 會從函數的當前位置向后執行到之后碰到的一個yield語句，會彈出值，并暫停函數執行。

再次調用next函數，和上一條一樣的處理結果

繼續調用哪個next函數，生成器函數如果結束執行了（顯示或隱式調用了return語句），會拋出StopIteration異常

4.2 使用場景

我們想要生成一個無限自然數的序列時，生成器就是一個很好的方式

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

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

4.3 協程coriutine

協程是生成器的一種高級方法，比進程、線程更輕量級，是在用戶空間調度函數的一種實現，Python 3 的asyncio就是協程實現，已經加入到了標準庫中，Python 3.5 使用async、await關鍵字直接原生支持寫成。協程在現階段來說比較復雜，后面會詳細進行說明，這里提一下實現思路：

有兩個生成器A、B

next(A)后，A執行到了yield語句后暫停，然后去執行next(B),B執行到yield語句也暫停，然后再次調用next(A)，再次調用next(B)

周而復始，就實現了調度的效果

還可以引入調度的策略來實現切換的方式

協程是一種非搶占式調度

4.4 yield from

在Python 3.3以后，出現了yield from語法糖。它的用法是

yield from 后面需要一個可迭代對象

yield from iterable?實際上等同于?for item in iterable: yield item

當然yield from也可以結合生成器來使用，因為生成器也是一個可迭代對象啊。

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