在傳統(tǒng)的遞歸中，典型的模式是，你執(zhí)行第一個(gè)遞歸調(diào)用，然后接著調(diào)用下一個(gè)遞歸來(lái)計(jì)算結(jié)果。這種方式中途你是得不到計(jì)算結(jié)果，知道所有的遞歸調(diào)用都返回。 這樣雖然很大程度上簡(jiǎn)潔了代碼編寫(xiě)，但是讓人很難它跟高效聯(lián)系起來(lái)。因?yàn)殡S著遞歸的深入，之前的一些變量需要分配堆棧來(lái)保存。

尾遞歸相對(duì)傳統(tǒng)遞歸，其是一種特例。在尾遞歸中，先執(zhí)行某部分的計(jì)算，然后開(kāi)始調(diào)用遞歸，所以你可以得到當(dāng)前的計(jì)算結(jié)果，而這個(gè)結(jié)果也將作為參數(shù)傳入下一次遞歸。這也就是說(shuō)函數(shù)調(diào)用出現(xiàn)在調(diào)用者函數(shù)的尾部，因?yàn)槭俏膊浚云溆幸粋€(gè)優(yōu)越于傳統(tǒng)遞歸之處在于無(wú)需去保存任何局部變量，從內(nèi)存消耗上，實(shí)現(xiàn)節(jié)約特性。
下面以遞歸計(jì)算加法的實(shí)例來(lái)說(shuō)明：

我們用python實(shí)現(xiàn)：

普通遞歸調(diào)用：

def recursion(n):
  if n==1:
    return n
  else:
    return n+recursion(n-1)

調(diào)用這個(gè)函數(shù)recursion（5），編譯器會(huì)執(zhí)行：

recursion(5)
5+recursion(4)
5+(4+recursion(3))
5+(4+(3+recursion(2)))
5+(4+(3+(2+recursion(1))))
5+(4+(3+(2+1)))
15

此處編譯器會(huì)分配遞歸棧來(lái)保存中間結(jié)果

下來(lái)看尾遞歸實(shí)現(xiàn)：

def tail_recursion(n,total=0):
  if n==0:
    return total
  else:
    return tail_recursion(n-1, total+n)

此時(shí)，編譯器做的工作：

tail_recursion(5,0)
tail_recursion(4,5)
tail_recursion(3,9)
tail_recursion(2,12)
tail_recursion(1,14)
tail_recursion(0,15)
15

你可以看到當(dāng)前時(shí)刻的計(jì)算值作為第二個(gè)參數(shù)傳入下一個(gè)遞歸，使得系統(tǒng)不再需要保留之前計(jì)算結(jié)果。

尾遞歸的優(yōu)勢(shì)就顯而易見(jiàn)了。

但是python本身不支持尾遞歸（沒(méi)有對(duì)尾遞歸做優(yōu)化），而且對(duì)遞歸的次數(shù)有限制，當(dāng)遞歸深度超過(guò)1000時(shí)，會(huì)拋出異常：

分別執(zhí)行recursion(998),tail_recursion(998,0)

輸出：

498501
498501

沒(méi)有問(wèn)題，當(dāng)調(diào)用

recursion(999),tail_recursion(999,0)時(shí)，

輸出：RuntimeError: maximum recursion depth exceeded

因?yàn)檫f歸次數(shù)超出了1000

有人對(duì)此為Python的尾遞歸寫(xiě)了一個(gè)優(yōu)化版本，讓Python突破遞歸調(diào)用1000次的限制：Tail Call Optimization Decorator (Python recipe)

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論