Swift 中的尾遞歸和彈床

NanSchroede 8年前發布 | 10K 次閱讀尾遞歸 Swift Apple Swift開發

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

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

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

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

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

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

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

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

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

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

用遞歸計算三角數

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

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

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

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

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

ttri(300) //45150

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

但是當輸入參數很大時，上面兩個方案都會 crash。我們來看一下如何用彈床算法來解決這個問題。

彈床

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

彈床形式的基本定義是循環的執行一個函數，這個函數要么返回的是一個用于下一次執行函數(以 thunk 或者“連續”的形式，具體說就是一個數據結構，其中包含用于某次方法調用所必須的信息)，要么返回的是一個其他類型的值(在這個例子中就是累加值)來標識迭代的結束。

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

更新

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

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

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

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

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

triCont(10, cont: id) // 55

感謝棒棒噠的解釋。

和直接執行遞歸調用不同的是，我們的 ttri 函數將會返回一個封裝了 真實的調用 的對象，并且一旦到達執行應該結束的點，我們會返回一個包含累加結果的哨兵值，來標識執行結束。

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

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

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

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)

仔細想一下上面的步驟，實現彈床的部分也就不難理解了。

在初始調用 ttri 方法啟動彈床之后， .Call 枚舉中包含的函數就被順序的執行，累加值也在每一步中被更新：

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

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

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

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

Update: @oisdk 建議說。 ttri 函數的實現可以通過一個快被遺忘的屬性修飾符 @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))
}

在我們繼續之前，再多說一點例子的問題。把代碼包在 while true 中并不是一個好習慣，一個更好的循環檢查應該是這樣：

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

當然還有更好的做法，因為我們用枚舉來關聯值，我們應該針對該枚舉實現一個比較運算符并在循環的開頭來檢查是否完成。

現在，彈床的基本原理已經解釋了，我們現在可以構建一個通用的函數來實現：給定一個返回 .Result 枚舉的函數，返回一個閉包來在彈床中執行原始函數。用該函數可以將執行細節封裝起來。

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 函數接收一個類型為 (V,A)->Result<A> 函數作為參數。這個函數之前我們已經實現了。還有一點和之前的版本顯著的不同的地方是，我們不能初始化泛型累加器 A 因為我們并不知道它具體的類型，所以我們將它暴露為我們返回的函數的參數，這里算一點小瑕疵。

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

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)

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

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

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

但是如果去掉傳統的彈床設計，我們可以簡化 Result 枚舉并且在彈床內部來跟蹤函數的執行，而不是把函數當做值存在枚舉中：

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 中遞歸的替代方案

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

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

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

或者我們可以創建一個 Sequence 或 Generator 來生成所有可能的三角形數的序列：

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 實現的兩種可能的替代方案。

結束語

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

絕壁沒有。

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

來自： http://swift.gg/2016/05/27/recursive-tail-calls-and-trampolines-in-swift/

本文由用戶 NanSchroede 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1464313246903.html

尾遞歸 Swift Apple Swift開發

Swift 中的尾遞歸和彈床

用遞歸計算三角數

彈床

Swift 中遞歸的替代方案

結束語

相關經驗

相關資訊

相關文檔

目錄