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

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

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

這很難理解（并且對(duì)于新程序員來說，它常常是難以理解），下面我們嘗試給函數(shù)添加一個(gè)L的打印并再次運(yùn)行它，從而在每個(gè)調(diào)用層級(jí)記錄下當(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

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