學(xué)習(xí)筆記
學(xué)習(xí)書目：《算法圖解》- Aditya Bhargava

---

文章目錄

• • • 遞歸
    • 基線條件和遞歸條件
    • 棧
    • • 調(diào)用棧
      • 遞歸調(diào)用棧

---

遞歸

首先，我們看一段代碼：

def print_num(my_list):for i in my_list:print(i)print_num([1, 3, 5, 7, 9])

輸出：

1 3 5 7 9

再看一段代碼：

def print_num2(my_list):if my_list:print(my_list.pop(0))print_num2(my_list)print_num2([1, 3, 5, 7, 9])

輸出：

1 3 5 7 9

我們看到的第一段代碼使用的是循環(huán)，第二段代碼使用的是遞歸，兩種方法結(jié)果相同。一般來說，遞歸能讓解決方案更清晰(雖然我舉的例子好像沒體現(xiàn)出來遞歸法更清晰)，但并沒有性能上的優(yōu)勢。實際上，在有些情況下，使用循環(huán)的性能更好。

如果使用循環(huán)，程序的性能可能更高；如果使用遞歸，程序可能更容易理解。如何選擇要看什么對你來說更重要。

基線條件和遞歸條件

由于遞歸函數(shù)調(diào)用自己，因此編寫這樣的函數(shù)時很容易出錯，進而導(dǎo)致無限循環(huán)。例如，假設(shè)我要編寫一個像下面這樣倒計時的函數(shù)：

def countdown(i): print(i) countdown(i-1)

如果我們運行上述代碼，將發(fā)現(xiàn)一個問題：這個函數(shù)運行起來沒完沒了！

編寫遞歸函數(shù)時，必須告訴它何時停止遞歸。正因為如此，每個遞歸函數(shù)都有兩部分：基線條件（base case）和遞歸條件（recursive case）。遞歸條件指的是函數(shù)調(diào)用自己，而基線條件則指的是函數(shù)不再調(diào)用自己，從而避免形成無限循環(huán)。

我們來給countdown函數(shù)添加一個基線條件：

def countdown(i): print(i)if i <= 1:returnelse:countdown(i-1)

現(xiàn)在，這個函數(shù)就會像預(yù)期那樣運行.

棧

假設(shè)我們有一疊便條，這疊便條記錄著我們馬上要做的待辦事項，我們簡稱這疊便條為清單。當(dāng)我們插入的待辦事項時，這個事件會放在清單的最上面；當(dāng)我們讀取待辦事項時，也只讀取清單最上面的那個，且讀完就將其銷毀。因此這個清單只有兩種操作：壓入（插入）和彈出（刪除并讀取）。

這種數(shù)據(jù)結(jié)構(gòu)被稱為棧。

調(diào)用棧

計算機在內(nèi)部使用被稱為調(diào)用棧的棧。

為了演示計算機是如何調(diào)用棧的，我們來看下面這個簡單的函數(shù)：

def greet(name):print(name, '!')greet2(name)print('too late!')bye()def greet2(name):print(name, '?')def bye():print('bye!')greet('maggie')

注意！print是一個函數(shù)，但是出于簡化考慮，我們假設(shè)它不是函數(shù)。

假設(shè)，我們調(diào)用greet('maggie')，計算機將首先為該函數(shù)調(diào)用分配一塊內(nèi)存空間：

變量name被賦值為maggie，這需要存儲到內(nèi)存中：

當(dāng)我們調(diào)用函數(shù)時，計算機會將函數(shù)調(diào)用涉及的所有變量的值存儲到內(nèi)存中。接下來，我們再調(diào)用greet2('maggie').同樣，計算機也為這個函數(shù)調(diào)用分配一塊內(nèi)存。

計算機使用一個棧來表示這些內(nèi)存塊，其中第二個內(nèi)存塊位于第一個內(nèi)存塊上面。我們打印maggie ?，然后從函數(shù)greet2的調(diào)用返回。此時，棧頂?shù)膬?nèi)存塊被彈出。

現(xiàn)在，棧頂?shù)膬?nèi)存塊是函數(shù)greet的，這意味著我們返回到了函數(shù)greet。當(dāng)我調(diào)用函數(shù)greet2時，函數(shù)greet只執(zhí)行了一部分。調(diào)用另一個函數(shù)時，當(dāng)前函數(shù)暫停并處于未完成狀態(tài)，該函數(shù)的所有變量的值仍在內(nèi)存中。

當(dāng)執(zhí)行完greet2函數(shù)后，我們繼續(xù)向下執(zhí)行，首先打印too late!，再調(diào)用函數(shù)bye()。計算機在棧頂添加了函數(shù)bye的內(nèi)存塊，然后我們打印bye!，并從該函數(shù)中返回。

現(xiàn)在，我們又回到了greet函數(shù)，由于無事可做，我們就從greet函數(shù)中返回。這個棧用于存儲多個函數(shù)的變量，故被稱為調(diào)用棧。

遞歸調(diào)用棧

遞歸函數(shù)也使用調(diào)用棧，我們來看看下面這個遞歸函數(shù)fact：

def fact(x):if x == 1:return 1else:return x*fact(x-1)print(fact(3))

輸出：

6

下面我們來看一下調(diào)用fact(3)時，調(diào)用棧的變化：

每個fact調(diào)用都有自己的x變量，在一個函數(shù)調(diào)用中不能訪問另一個函數(shù)的x變量。

總結(jié)

以上是生活随笔為你收集整理的小白的算法初识课堂(part3)--递归的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。