1. 遞歸指的是調(diào)用自己的函數(shù)
遞歸函數(shù)有兩部分：基線條件（base case）和遞歸條件（recursive case）。遞歸條件指的是函數(shù)調(diào)用自己，而基線條件則指的是函數(shù)不再調(diào)用自己，從而避免形成無限循環(huán)。

def countdown(i):
    print(i)
    if i <= 0: # 基線條件
        return
    else: # 遞歸條件
        countdown(i-1)
countdown(5)

運(yùn)行結(jié)果如下:

運(yùn)行結(jié)果.png

2. 棧(stack)
遞歸函數(shù)factorial的調(diào)用棧(call stack)。factorial(5)寫作5!，其定義如下：5! = 5 * 4 * 3 * 2 * 1。同理，factorial(3)為3 * 2 * 1。下面是計(jì)算階乘的遞歸函數(shù)。

def fact(x):
    if x == 1:
        return 1
    else:
        return x * fact(x - 1)
print(fact(5))
# 輸出結(jié)果為 120

小結(jié)

• 棧有兩種操作：壓入和彈出
• 所有函數(shù)調(diào)用都進(jìn)入調(diào)用棧
• 使用棧雖然很方便，但是也要付出代價(jià)：存儲(chǔ)詳盡的信息可能占用大量的內(nèi)存。每個(gè)函數(shù)調(diào)用都要占用一定的內(nèi)存，如果棧很高，就意味著計(jì)算機(jī)存儲(chǔ)了大量函數(shù)調(diào)用的信息。

• Leigh Caldwell在Stack Overflow上說的一句話：“如果使用循環(huán)，程序的性能可能更高；如果使用遞歸，程序可能更容易理解。如何選擇要看什么對(duì)你來說更重要。