以階乘運(yùn)算為例。階乘本身其實(shí)不應(yīng)該陷入到自我調(diào)用的遞歸圈中，正如繪畫的艾舍爾應(yīng)該置身怪圈之外。遞歸僅應(yīng)該出現(xiàn)在遞進(jìn)的運(yùn)算中，每次遞進(jìn)的結(jié)果則作為參數(shù)傳入到遞歸的函數(shù)中。正如SICP對(duì)階乘運(yùn)算的分析。線性遞歸的算法體現(xiàn)的是階乘運(yùn)算的樸素?cái)?shù)學(xué)知識(shí)，即：對(duì)于一個(gè)正整數(shù)n，n!就等于n乘以(n-1)!。

除此之外，SICP給出了另外一種觀察的視角：

我們可以將計(jì)算階乘n!的規(guī)則描述為：先乘1和2，而后將得到的結(jié)果乘以3，而后再乘以4，這樣下去直到達(dá)到n。更形式地說(shuō)，我們要維持著一個(gè)變動(dòng)中的乘積product，以及一個(gè)從1到n的計(jì)數(shù)器counter。

我們需要將計(jì)數(shù)器counter與變動(dòng)的乘積product抽離出來(lái)，放到如侯世達(dá)所說(shuō)的“可見(jiàn)的層次結(jié)構(gòu)”中，即單獨(dú)定義一個(gè)函數(shù)factIter：

def factorial(n: Int): Long = {
  def factIter(product: Long, counter: Int, maxCount:Int): Long =
    if (counter > maxCount) product
    else factIter(product * counter, counter+1, maxCount)
  factIter(1, 1, n)
}

在factorial函數(shù)內(nèi)部定義的函數(shù)factIter實(shí)現(xiàn)了遞歸，它有一個(gè)特征是方法的尾部是且只能是對(duì)函數(shù)自身的調(diào)用。

product變量就是前面我所謂的“每次遞進(jìn)的結(jié)果”，也就是SICP中提到的“變動(dòng)中的乘積”。準(zhǔn)確來(lái)講，應(yīng)該將product看作是一個(gè)accumulator。它每次存儲(chǔ)的都是每一步計(jì)算的結(jié)果，然后通過(guò)其匯集，最后收獲最終的運(yùn)算結(jié)果。至于counter與maxCount變量的引入，不過(guò)是為了完成遞進(jìn)的運(yùn)算，以及給出終止運(yùn)算的滿足條件而已。

SICP認(rèn)為：

（這種運(yùn)算過(guò)程）并沒(méi)有任何增長(zhǎng)或者收縮。對(duì)于任何一個(gè)n，在計(jì)算過(guò)程中的每一步，在我們需要保存的軌跡里，所有的東西就是變量product、counter和maxCount的當(dāng)前值。我們稱這種過(guò)程為一個(gè)迭代過(guò)程（iterative process）……在計(jì)算n!時(shí)，所需的計(jì)算步驟隨著n線性增長(zhǎng)，因而被稱為線性迭代過(guò)程（linear iterative process）。

由于其特性是內(nèi)部的函數(shù)總是在函數(shù)尾部被遞歸調(diào)用，故而這種調(diào)用方式又被稱之為尾遞歸（tail recursive）。它的執(zhí)行過(guò)程如下圖所示：

計(jì)算6!的線性迭代過(guò)程，圖片來(lái)自SICP

我們可以比較前面線性遞歸過(guò)程的執(zhí)行結(jié)果，很顯然，線性迭代過(guò)程的執(zhí)行步驟要遠(yuǎn)遠(yuǎn)少于前者。本質(zhì)上，雖然尾遞歸名為“遞歸”，其實(shí)執(zhí)行的是一個(gè)迭代過(guò)程。在Scala或者其他很多語(yǔ)言中，尾遞歸就是一種編譯技巧。例如當(dāng)Scala發(fā)現(xiàn)某個(gè)遞歸調(diào)用其實(shí)是一個(gè)尾遞歸時(shí)，會(huì)自動(dòng)將該遞歸編譯為循環(huán)迭代，從而避免了每次進(jìn)行棧的操作（因?yàn)檫f歸需要記錄延遲運(yùn)算）。Scala還提供了@tailrec標(biāo)記來(lái)標(biāo)識(shí)尾遞歸。若你編寫的遞歸函數(shù)不是尾遞歸，只要標(biāo)記了@tailrec，編譯時(shí)會(huì)提示錯(cuò)誤。

要將一個(gè)遞歸過(guò)程編寫為迭代過(guò)程，而又要避免顯示地循環(huán)調(diào)用方式，關(guān)鍵之處就在于我們要轉(zhuǎn)換視角（跳出互相繪制的兩只手）。個(gè)人認(rèn)為，“四兩撥千斤”的著眼點(diǎn)就是尋找accumulator。

我在項(xiàng)目中希望對(duì)一個(gè)類似樹(shù)結(jié)構(gòu)的樣例類做一次“拍平”的操作。定義如下：

case class BindingElement(itemType: BindingItemType, fieldId: ID, children: Option[List[BindingElement]])

BindingElement的內(nèi)部“可能”嵌套了子的BindingElement列表。而子列表中的BindingElement也可能繼續(xù)嵌套。如此的嵌套自然就形成了一棵樹(shù)，且非最簡(jiǎn)單的二叉樹(shù)。

需求要求將根節(jié)點(diǎn)BindingElement嵌套的所有子節(jié)點(diǎn)（包括間接嵌套）全部拍平，最后形成一個(gè)沒(méi)有任何子節(jié)點(diǎn)的BindingElement列表。

我在實(shí)現(xiàn)時(shí)，直覺(jué)告訴我這個(gè)“拍平”的動(dòng)作其實(shí)就是對(duì)一棵樹(shù)的遍歷，完全可以用尾遞歸來(lái)完成?？墒菍懥嗽S久，都未能將這個(gè)尾遞歸函數(shù)實(shí)現(xiàn)。問(wèn)題的癥結(jié)就是我沒(méi)有去尋找關(guān)鍵的accumulator。實(shí)質(zhì)上，針對(duì)這個(gè)場(chǎng)景，我們要返回的結(jié)果是List[BindingElement]，在迭代過(guò)程中，就是每次疊加的值。初始值則為Nil。這里沒(méi)有階乘運(yùn)算中的counter與maxCount，而是一個(gè)作為children的List[BindingElement]。因?yàn)閰⑴c遞歸的結(jié)構(gòu)是列表中每個(gè)BindingElement中的children，對(duì)于List而言，我們可以判斷其值是否為Nil來(lái)作為終止條件。

找到了accumulator，尾遞歸的迭代算法自然就水到渠成了。代碼如下所示：

case class BindingElement(itemType: BindingItemType, fieldId: ID, children: Option[List[BindingElement]]) { 
  def flatten:List[BindingElement] = { 
    def cloneToLeaf(item: BindingElement) = BindingElement(item.itemType, item.fieldId, None) 

    @tailrec 
    def traverse(items: List[BindingElement], acc: List[BindingElement]): List[BindingElement] = 
      items match { 
        case Nil => acc 
        case head :: tail => traverse(head.children.getOrElse(Nil) ::: tail, acc :+ cloneToLeaf(head)) 
      }

    traverse(children.getOrElse(Nil), List[BindingElement](cloneToLeaf(this))) 
  } 
}

注意，這里的acc（即accumulator）在Scala中其實(shí)是一個(gè)不變的變量；所以通過(guò)運(yùn)算符:+添加元素項(xiàng)后得到的是另外一個(gè)List。然而，作為accumulator，其實(shí)它是以參數(shù)形式傳遞給下一個(gè)迭代，故而下一次迭代中的acc已經(jīng)變成了累加了元素后的結(jié)果，這是traverse函數(shù)之所以能夠奏效的原因。

因?yàn)槲策f歸函數(shù)tranverse遍歷的是List[BindingElement]，這會(huì)導(dǎo)致返回的結(jié)果會(huì)缺失根元素自身，所以在初始化acc時(shí)，將根元素（即this）賦值給了acc。

遞歸充滿了藝術(shù)的神秘美感，而尾遞歸則在藝術(shù)美與工程高效之間取得了平衡?！懂嬍帧返膬蓚€(gè)層次（可見(jiàn)的和不可見(jiàn)的）給了我們一個(gè)啟發(fā)，就是在觀察事物時(shí)，需要嘗試不同的視角，要學(xué)會(huì)跳出具體的實(shí)現(xiàn)細(xì)節(jié)，找到職責(zé)上的抽象分解。對(duì)于程序員而言，我們還可以嘗試跳出計(jì)算機(jī)科學(xué)的范疇，從繪畫、數(shù)學(xué)、建筑或者音樂(lè)中尋找到靈感，利用跨界思想來(lái)體悟軟件設(shè)計(jì)與編程。