作者：uraimo，原文鏈接，原文日期：2016-05-05
譯者：aaaron7；校對：numbbbbb；定稿：shanks

通過遞歸來實現(xiàn)算法往往比基于循環(huán)的實現(xiàn)來得更加清晰，但遞歸的實現(xiàn)會因為每次方法調(diào)用的時候都需要分配和管理棧幀而導(dǎo)致額外的開銷，這會導(dǎo)致遞歸的實現(xiàn)很慢而且有可能很快就耗盡了棧空間(也就是棧溢出)。

為了避免棧溢出，一個推薦的做法是把程序重寫成尾遞歸的形式來利用一些編譯器的尾遞歸優(yōu)化的功能來避免溢出。

但我們不僅會想，普通遞歸和尾遞歸的區(qū)別到底是什么？編譯器的尾遞歸優(yōu)化到底是做了怎樣的事情？

尾遞歸和普通的遞歸不同之處在于，尾遞歸函數(shù)的返回值是簡單的遞歸調(diào)用，沒有任何額外的運算。實際運算的過程是通過一個累加器變量一路傳遞到后繼的調(diào)用中，直到遞歸執(zhí)行完畢。

上面的定義可能不太好懂，下一節(jié)會有一個例子來提供更清晰的解釋?，F(xiàn)在你唯一需要知道的就是，有一種特殊的遞歸可以被編譯器優(yōu)化成更高效的基于循環(huán)的實現(xiàn)，不會受到棧大小的影響。

但是在 Swift 里，我們不能指望編譯器會在所有情況下都執(zhí)行尾遞歸優(yōu)化。

這個缺陷之前已經(jīng)在 Natasha 的博客 被討論過，現(xiàn)在已經(jīng)有人為此做了一些工作并提交了一份提案。提案主要提出了添加一些屬性來讓優(yōu)化器的行為更加可驗證，并允許明確地指定哪些尾遞歸是可以被優(yōu)化的(如果沒有被優(yōu)化，則應(yīng)該拋出異常。)

這篇文章我們會講解如何使用蹦床 (trampolines) 機制來解決 Swift 尾遞歸優(yōu)化方面的不足，同時會給出一些遞歸的替代方案。

譯者注：為什么叫做蹦床呢？是因為蹦床機制本質(zhì)上就是把遞歸調(diào)用轉(zhuǎn)化為循環(huán)調(diào)用。遞歸會先連續(xù)的壓棧(遞歸調(diào)用)，返回的時候再連續(xù)地出棧。而蹦床的話，每次執(zhí)行調(diào)用壓棧一次(函數(shù)調(diào)用),然后馬上出棧(函數(shù)返回)。循環(huán)往復(fù)這個過程。如果把棧比作蹦床的話，這個過程就像在跳蹦床一樣。落下就是壓棧，彈起就是出棧。交替進行。

可以到 GitHub 或者這里獲得本文所使用的 playground 文件

用遞歸計算三角數(shù)

讓我們來看一個用遞歸的方式來計算第 n 個三角形數(shù)的算法：

func tri(n:Int)->Int{
    if n <= 0 {
        return 0
    }
    return n+tri(n-1)
}
tri(300) //45150

在這個簡單的遞歸的例子中，遞歸調(diào)用的執(zhí)行結(jié)果和參數(shù)相加就是結(jié)果。我們最初的 tri(300) 的結(jié)果就是對所有這樣的數(shù)，通過遞歸鏈式地求和。

把上述代碼改為尾遞歸的形式，我們添加一個累加器變量來把累加值傳遞到下一層調(diào)用。

func ttri(n:Int, acc:Int=0)->Int {
    if n<1 {
        return acc
    }
    return ttri(n-1,acc:acc+n)
}

ttri(300) //45150

注意上述算法中結(jié)果是如何通過累加器實現(xiàn)的，最后一步就是簡單的返回累加值來完整整個計算過程。

但是當(dāng)輸入?yún)?shù)很大時，上面兩個方案都會 crash。我們來看一下如何用蹦床算法來解決這個問題。

蹦床

蹦床背后的原理其實很簡單。

蹦床形式的基本定義是循環(huán)的執(zhí)行一個函數(shù)，這個函數(shù)要么返回的是一個用于下一次執(zhí)行函數(shù)(以 thunk 或者“連續(xù)”的形式，具體說就是一個數(shù)據(jù)結(jié)構(gòu)，其中包含用于某次方法調(diào)用所必須的信息)， 要么返回的是一個其他類型的值(在這個例子中就是累加值)來標識迭代的結(jié)束。

如果我們要用蹦床來順序的執(zhí)行我們的尾遞歸函數(shù)，我們需要對其進行一些簡單的修改，修改成連續(xù)傳遞的形式 (continuation-passing style).

更新

像 oisdk 所說，我們在下面修改后的函數(shù)只是有一點點像真正的 CPS(譯注：也就是上面提到的連續(xù)傳遞形式)。

在這里，閉包可以讓你通過模擬延遲計算 (Lazy Evaluation) 來實現(xiàn)一種偽尾遞歸優(yōu)化。在連續(xù)傳遞形式中，你將“連續(xù)”以函數(shù)的額外參數(shù)的形式傳到遞歸函數(shù)中，“連續(xù)”定義了函數(shù)主體執(zhí)行完畢以后該做什么（譯注：本質(zhì)上來說，“連續(xù)”也是一個函數(shù)）。簡單的說，先執(zhí)行函數(shù)主體，然后執(zhí)行“連續(xù)”的部分，通常在最開始，你傳入的是一個元函數(shù)。這個機制可以讓你把普通遞歸函數(shù)變換為尾遞歸函數(shù)。但顯然，Swift 并不保證進行尾遞歸優(yōu)化，所以其實這個機制也沒什么用處。

先不管這些。下面是三角數(shù)計算的 CPS 形式：

func triCont(n: Int, cont: Int -> Int) -> Int {
return n <= 1 ? cont(1) : triCont(n-1) { r in cont(r+n) }
}

func id<A>(x: A) -> A { return x }

triCont(10, cont: id) // 55

感謝棒棒噠的解釋。

和直接執(zhí)行遞歸調(diào)用不同的是，我們的 ttri 函數(shù)將會返回一個封裝了真實的調(diào)用的對象，并且一旦到達執(zhí)行應(yīng)該結(jié)束的點，我們會返回一個包含累加結(jié)果的哨兵值，來標識執(zhí)行結(jié)束。

我們從定義一個 Result 枚舉來表示我們修改后的遞歸函數(shù)可能返回的值：.Done 表示遞歸執(zhí)行完畢，并且其中包含最后的累加值。.Call 會包含下一步要執(zhí)行的方法的閉包。

enum Result<A>{
    case Done(A)
    case Call(()->Result<A>)
}

現(xiàn)在我們就可以來定義新的函數(shù)，包括一個修改版的 ttri 以及一些實現(xiàn)蹦床機制的代碼。最后一個部分一般放在單獨的函數(shù)中。但是在本例里把都放到一起，為了更加可讀：

func tritr(n:Int)->Int {
    func ttri(n:Int, acc:Int=0)->Result<Int> {
        if n<1 {
            return .Done(acc)
        }
        return .Call({
            ()->Result<Int> in
            return ttri(n-1,acc: acc+n)
        })
    }
    
    // Trampoline section
    let acc = 0
    var res = ttri(n,acc:acc)
    
    while true {
        switch res {
        case let .Done(accu):
            return accu
        case let .Call(f):
            res = f()
        }
    }
}

tritr(300)

仔細想一下上面的步驟，實現(xiàn)蹦床的部分也就不難理解了。

在初始調(diào)用 ttri 方法啟動蹦床之后，.Call 枚舉中包含的函數(shù)就被順序的執(zhí)行，累加值也在每一步中被更新：

return .Call({
    ()->Result<Int> in
    return ttri(n-1,acc: acc+n)
})

雖然代碼不一樣了，但是行為仍然和我們最開始的遞歸版本是一樣的。

一旦計算完成，ttri 函數(shù)就返回一個包含最終結(jié)果的 .Done 枚舉。

雖然這個實現(xiàn)比最開始的版本要慢，因為所有代碼都需要操作蹦床。但這個版本已經(jīng)解決了棧溢出這個最大的問題，我們現(xiàn)在已經(jīng)可以計算任意大小三角數(shù)了，直到超過整數(shù)的限制。

Update: @oisdk 建議說。ttri函數(shù)的實現(xiàn)可以通過一個快被遺忘的屬性修飾符 @autoclosure 來簡化。

func call<A>(@autoclosure(escaping) c: () -> Result<A>) -> Result<A> {
    return .Call(c)
}

func ttri(n: Int, acc:Int=1) -> Result<Int> {
    return n <= 1 ? .Done(acc) : call(tri(n-1, acc: acc+n))
}

在我們繼續(xù)之前，再多說一點例子的問題。把代碼包在 while true 中并不是一個好習(xí)慣，一個更好的循環(huán)檢查應(yīng)該是這樣：

while case .Call(_) = res {
    switch res {
    case let .Done(accu):
        return accu
    case let .Call(f):
        res = f()
    }
}
    
if case let .Done(ac) = res {
    return ac
}
    
return -1

當(dāng)然還有更好的做法，因為我們用枚舉來關(guān)聯(lián)值，我們應(yīng)該針對該枚舉實現(xiàn)一個比較運算符并在循環(huán)的開頭來檢查是否完成。

現(xiàn)在，蹦床的基本原理已經(jīng)解釋了，我們現(xiàn)在可以構(gòu)建一個通用的函數(shù)來實現(xiàn)：給定一個返回 .Result 枚舉的函數(shù)，返回一個閉包來在蹦床中執(zhí)行原始函數(shù)。用該函數(shù)可以將執(zhí)行細節(jié)封裝起來。

func withTrampoline<V,A>(f:(V,A)->Result<A>) -> ((V,A)->A){
    return { (value:V,accumulator:A)->A in
        var res = f(value,accumulator)
        
        while true {
            switch res {
            case let .Done(accu):
                return accu
            case let .Call(f):
                res = f()
            }
        }
    }
}

在我們返回的閉包的主體基本上就是我們在之前例子中的蹦床部分，withTrampoline 函數(shù)接收一個類型為 (V,A)->Result<A> 函數(shù)作為參數(shù)。這個函數(shù)之前我們已經(jīng)實現(xiàn)了。還有一點和之前的版本顯著的不同的地方是，我們不能初始化泛型累加器 A 因為我們并不知道它具體的類型，所以我們將它暴露為我們返回的函數(shù)的參數(shù)，這里算一點小瑕疵。

下面就用一下我們剛才定義的通用函數(shù):

var fin: (n:Int, a:Int) -> Result<Int> = {_,_ in .Done(0)}
fin = { (n:Int, a:Int) -> Result<Int> in
    if n<1 {
        return .Done(a)
    }
    return .Call({
        ()->Result<Int> in
        return fin(n: n-1,a: a+n)
    })
}

let f = withTrampoline(fin)

f(30,0)

這代碼可能比你想象的要長一點。

因為我們在閉包內(nèi)部需要使用當(dāng)前的函數(shù)，所以我們必須在定義真正的閉包之前先定義一個該閉包類型的傀儡實現(xiàn)，來使得在閉包實現(xiàn)中對自身的引用合法化。

如果不用傀儡實現(xiàn)，而是直接聲明 fin 閉包，會得到一個變量在它初始化過程中被使用的錯誤。 如果你喜歡冒險，可以嘗試使用 Z 組合子 來替換這個丑陋的解決辦法。

但是如果去掉傳統(tǒng)的蹦床設(shè)計，我們可以簡化 Result 枚舉并且在蹦床內(nèi)部來跟蹤函數(shù)的執(zhí)行，而不是把函數(shù)當(dāng)做值存在枚舉中：

enum Result2<V,A>{
    case Done(A)
    case Call(V, A)
}

func withTrampoline2<V,A>(f:(V,A)->Result2<V,A>) -> ((V,A)->A){
    return { (value:V,accumulator:A)->A in
        var res = f(value,accumulator)
        
        while true {
            switch res {
            case let .Done(accu):
                return accu
            case let .Call(num, accu):
                res = f(num,accu)
            }
        }
    }
}

let f2 = withTrampoline2 { (n:Int, a:Int) -> Result2<Int, Int> in
    if n<1 {
        return .Done(a)
    }
    return .Call(n-1,a+n)
}

f2(30,0)

這樣看起來更清晰，更緊湊。

可以到 Github 或者這里獲得本文所使用的 playground 文件

Swift 中遞歸的替代方案

如果你有閱讀過一些關(guān)于 Swift 函數(shù)式編程的文章的話那你應(yīng)該知道 Swift 提供了一些有用的特性來替代遞歸來解決一些一般會使用遞歸來解決的問題。

比如，三角形數(shù)可以通過一行簡單的函數(shù)式代碼計算出來，使用 reduce:

(1...30).reduce(0,combine:+) //465

或者我們可以創(chuàng)建一個 Sequence 或 Generator 來生成所有可能的三角形數(shù)的序列：

class TriangularSequence :SequenceType {
    func generate() -> AnyGenerator<Int> {
        var i = 0
        var acc = 0
        return AnyGenerator(body:{
            print("# Returning "+String(i))
            i=i+1
            acc = acc + i
            return acc
        })
    }
}

var fs = TriangularSequence().generate()

for i in 1...30 {
    print(fs.next())
}

以上就是我們可以用 Swift 實現(xiàn)的兩種可能的替代方案。

結(jié)束語

這篇文章描述了 Swift 中遞歸處理的一些限制以及在 Swift 中如何實現(xiàn)蹦床(在缺乏尾遞歸優(yōu)化的語言中一種常規(guī)的優(yōu)化機制)。但是我提倡在代碼中使用蹦床了嗎？

絕壁沒有。

在 Swift 中，考慮到它并不是純函數(shù)式的語言，一般能夠被復(fù)雜的蹦床解決的問題，我們總是可以通過一些語言特性以一個更好的方式去解決(代碼更加可讀，行為更加可理解)。不要對代碼做過度的設(shè)計，未來的你會感謝你自己的。

再次感謝 @oisdk 極富洞察力的評論。

可以在 Twitter 上關(guān)注我。

本文由 SwiftGG 翻譯組翻譯，已經(jīng)獲得作者翻譯授權(quán)，最新文章請訪問 http://swift.gg。