使用延續到二進制遞歸轉換爲尾遞歸

Question

正如我在讀編程F＃的書，我發現195頁的示例代碼片段如下：

type ContinuationStep<'a> = 
    | Finished 
    | Step of 'a * (unit -> ContinuationStep<'a>) 

let iter f binTree = 
    let rec linearize binTree cont = 
    match binTree with 
    | Empty -> cont() 
    | Node(x, l, r) -> 
     Step(x, (fun() -> linearize l (fun() -> linearize r cont))) 

    let steps = linearize binTree (fun() -> Finished) 

    let rec processSteps step = 
    match step with 
    | Finished ->() 
    | Step(x, getNext) 
     -> f x 
     processSteps (getNext()) 

    processSteps steps 

通過使用延續，穿越的二進制遞歸二進制已被轉換爲尾遞歸函數processSteps。我的問題是，另一個函數linearize似乎是非尾遞歸的。這是否意味着即使使用延續，我們也不能將二元遞歸轉換爲尾遞歸？

Answer 1

這個例子有點微妙，因爲它不使用普通延續，而是建立一個可以逐步評估的結構。在通常進行遞歸調用的地方，它將返回一個值Step，其中包含您要遞歸調用的函數。

在第二種情況下，linearize函數返回一個包含將調用linearize遞歸函數一個Step，但它不會立即使遞歸調用。所以函數不會進行遞歸調用（它只是存儲遞歸引用）。

很有道理考慮程序是否是尾遞歸，當你看processSteps，因爲執行實際的循環 - 這是尾遞歸，因爲它運行一個Step通過Step不保持堆棧空間爲每Step。

如果你想建立一個列表，而不是懶步驟鏈，那麼你就必須做出遞歸調用linearize立即延續裏面：

let rec linearize binTree cont = 
    match binTree with 
    | Empty -> cont [] 
    | Node(x, l, r) -> 
     linearize l (fun l -> linearize r (fun v -> cont (x::v))) 

這在本質上是一樣的前面函數，但它實際上調用linearize而不是構建Step，其中包含一個函數，該函數將調用linearize。

Answer 2

linearize是尾遞歸：你不需要從遞歸調用回來繼續計算。

fun() -> linearize l (fun() -> linearize r cont) 

不叫linearize。計算被暫停，直到processSteps調用getNext()。