在前面的文章中，我們說到了可以使用循環(huán)語句來替代遞歸。但是，有時候必須使用遞歸，或者說使用遞歸才是更方便的解決方案。

考慮像下面這樣的一個任務(wù)：計算一個嵌套的子列表結(jié)構(gòu)中所有數(shù)字的總和：

[1,[2,[3,4],5],6,[7,8]] # Arbitrarily nested sublists

簡單的循環(huán)語句在這里不起作用，因為這不是一個線性迭代。嵌套的循環(huán)語句也不夠用，因為子列表可能嵌套到任意的深度并且以任意的形式嵌套。相反，下面的代碼使用遞歸來對應(yīng)這種一般性的嵌套，可以順序地訪問子列表：

def sumtree（L）:

tot = 0

for x in L:                                # For each item at this level

    if not isinstance（x,list）:

        tot += x                           # Add numbers directly

    else:

        tot += sumtree（x）                  # Recur for sublists

return tot

L = [1,[2,[3,4],5],6,[7,8]] # Arbitrary nesting

print（sumtree（L）） # Prints 36

Pathological cases

print（sumtree（[1,[2,[3,[4,[5]]]]]）） # Prints 15 （right-heavy）

print（sumtree（[[[[[1],2],3],4],5]）） # Prints 15 （left-heavy）

盡管出于簡單性和高效率的目的，對于線性迭代通常應(yīng)該使用循環(huán)語句而不是遞歸，但我們會發(fā)現(xiàn)像上面示例一樣的必須使用遞歸的情況還是很多的。