Python支持遞歸函數(shù)——即直接或間接地調(diào)用自身以進(jìn)行循環(huán)的函數(shù)。遞歸是頗為高級的話題，并且它在Python中相對少見。然而，它是一項(xiàng)應(yīng)該了解的有用的技術(shù)，因?yàn)樗试S程序遍歷擁有任意的、不可預(yù)知的形狀的結(jié)構(gòu)。遞歸甚至是簡單循環(huán)和迭代的替換，盡管它不一定是最簡單的或最高效的一種。

要對一個數(shù)字列表（或者其他序列）求和，我們可以使用內(nèi)置的sum函數(shù)，或者自己編寫一個更加定制化的版本。這里我們就用遞歸來編寫一個定制求和函數(shù)：

def mysum（L）:

... if not L:

... return 0

... else:

... return L[0] + mysum（L[1:]） # Call myself

mysum（[1,2,3,4,5]）

15

在每一層，這個函數(shù)都遞歸地調(diào)用自己來計算列表剩余的值的和，這個和隨后加到前面的一項(xiàng)中。當(dāng)列表變?yōu)榭盏臅r候，遞歸循環(huán)結(jié)束并返回0。當(dāng)像這樣使用遞歸的時候，對函數(shù)調(diào)用的每一個打開的層級，在運(yùn)行時調(diào)用堆棧上都有自己的一個函數(shù)本地作用域的副本，也就是說，這意味著L在每個層級都是不同的。

這很難理解（并且對于新程序員來說，它常常是難以理解），下面我們嘗試給函數(shù)添加一個L的打印并再次運(yùn)行它，從而在每個調(diào)用層級記錄下當(dāng)前的列表：

def mysum（L）:

... print（L） # Trace recursive levels

... if not L: # L shorter at each level

... return 0

... else:

... return L[0] + mysum（L[1:]）

...

mysum（[1,2,3,4,5]）

[1,2,3,4,5]

[2,3,4,5]

[3,4,5]

[4,5]

[5]

[]

15

正如你所看到的，在每個遞歸層級上，要加和的列表變得越來越小，直到它變?yōu)榭铡f歸循環(huán)結(jié)束。加和隨著遞歸調(diào)用的展開而計算出來。