1. 遞歸

循環和遞歸可以實現相同的功能，如：

• 循環

def look_for_key(main_box)pile = main_box.make_a_pile_to_look_thorugh()while pile is not empty:box = pile.grab_a_box()for item in box:if item.is_a_box():pile.append(item)elif item.is_a_key():print "find the key!"

• 遞歸

def look_for_key(box)for item in box:if item.is_a_box():look_for_key(item)elif item.is_a_key():print "find the key!"

如果使用循環，程序的性能可能更高；如果使用遞歸，程序可能更容易理解。

1.1 基線條件和遞歸條件

編寫遞歸函數時，必須告訴它何時停止遞歸。因此，每個遞歸函數都有兩個部分：基線條件和遞歸條件。遞歸條件指的時函數調用自身，而基線條件指的是函數不調用自己，從而避免形成無限循環。

def countdown(i)print iif i < 1:  //基線條件returnelse      //遞歸條件countdown(i)

2. 棧

棧是一種簡單的數據結構。
數據存儲和讀取特點是：“先進后出”。
具備兩種操作：壓入（插入）和彈出（刪除并讀取）。

2.1 調用棧

計算機在內部使用被稱為調用棧的棧。
當在一個函數中調用多個另外的函數時：調用另一個函數時，當前函數暫定并處于未完成狀態。只有先執行完調用函數，再回到當前函數進行執行。
計算機使用一個棧來表示函數的內存塊（調用函數時，函數調用涉及的所有變量的指存儲在內存中）。
棧用于存儲多個函數的變量，被稱為調用棧。

2.2 遞歸調用棧

def fact(x)if x == 1:  //基線條件return 1else      //遞歸條件return fact(x-1)*x

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

使用棧雖然很方便，但是也是需要付出代價：存儲詳盡的信息可能占用大量的內存。每個函數調用都要占用一定的內存，如果棧很高，就意味著計算機存儲了大量函數調用的信息。此時可以選擇：重新編寫代碼，轉而使用循環；使用尾遞歸。