每天學習一點兒演算法-遞歸
遞歸是很多演算法都使用的一種編程方法。聽說遞歸是一種十分優雅的問題解決辦法，可是對於初涉遞歸的我，還沒有形成這種獨特的體會。
學習使用遞歸的關鍵在於：如何將問題分為基線條件和遞歸條件。
基線條件和遞歸條件
由於遞歸函數調用自己，因此編寫這樣的函數時很容易出錯，進而導致無限循環。
例如下面這個函數：
假設i的初始值為3，運行上述代碼後：
它會一直運行下去，（可按Ctrl+C停止）
所以，編寫遞歸函數必須要讓函數能在某個時候停止遞歸。
讓遞歸函數停止遞歸的條件就是基線條件。
遞歸條件指函數調用自己；基線條件指函數不再調用自己。
現在我們給函數countdown添加基線條件：
運行結果：
棧
使用遞歸必須就要理解一個名為「調用棧」的編程概念。因為遞歸函數在運行的過程中是存儲在棧中的。
棧是一種數據結構，只有兩種基本操作：壓入（進棧）和彈出（出棧）。且遵循後進先出的規則。
計算機在內部使用的棧被稱為調用棧。下面用一個函數來看看計算機如何使用調用棧：
這個函數問候用戶，再調用了另外兩個函數，這兩個函數的代碼如下：
注釋：在python中，print也是一個函數，但我們先暫且不考慮它。
假設我們調用greet(「you」)。計算機先為其分配一塊內存：
接下來，列印出。再調用函數greet2(「you」)。同樣，計算機也為這個函數調用分配一個內存塊：
然後列印出。然後從函數調用返回。此時，棧頂的內存塊被彈出：
執行完函數greet2後，回到函數greet，並從離開的地方接著往下執行：首先列印。再調用函數bye：
然後列印。並從這個函數返回。
現在又回到了函數greet。由於沒有別的事要做，就從函數greet返回。這個被用於存儲多個函數變數的棧，稱之為調用棧。
遞歸調用棧的另一個應用就是計算階乘。下面是一個計算階乘的遞歸函數：
我們來分析一下調用fact(3)時，調用棧是如何變化的：
說明：
尾遞歸
最後介紹一個尾遞歸。尾遞歸是一種高級遞歸，它和普通遞歸函數的區別在於：尾遞歸在函數執行的最後一步調用自身，而其他遞歸函數在函數的最後一步不僅調用了自身，還摻雜著其他表達式。
舉個例子：
計算階乘：
這不是尾遞歸函數。
這就是尾遞歸函數。
小結
每天學習一點點，每天進步一點點。
TAG:小白客 |