Python支持遞歸函數(shù)

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

要對一個數(shù)字列表（或者其他序列）求和，我們可以使用內置的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ù)都遞歸地調用自己來計算列表剩余的值的和，這個和隨后加到前面的一項中。當列表變?yōu)榭盏臅r候，遞歸循環(huán)結束并返回0。當像這樣使用遞歸的時候，對函數(shù)調用的每一個打開的層級，在運行時調用堆棧上都有自己的一個函數(shù)本地作用域的副本，也就是說，這意味著L在每個層級都是不同的。

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

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)結束。加和隨著遞歸調用的展開而計算出來。