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

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

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

簡(jiǎn)單的循環(huán)語(yǔ)句在這里不起作用，因?yàn)檫@不是一個(gè)線性迭代。嵌套的循環(huán)語(yǔ)句也不夠用，因?yàn)樽恿斜砜赡芮短椎饺我獾纳疃炔⑶乙匀我獾男问角短?。相反，下面的代碼使用遞歸來(lái)對(duì)應(yīng)這種一般性的嵌套，可以順序地訪問(wèn)子列表：

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）

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