使用延续到二进制递归转换为尾递归

问题描述：

正如我在读编程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似乎是非尾递归的。这是否意味着即使使用延续，我们也不能将二元递归转换为尾递归？

答

这个例子有点微妙，因为它不使用普通延续，而是建立一个可以逐步评估的结构。在通常进行递归调用的地方，它将返回一个值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。

答

linearize是尾递归：你不需要从递归调用回来继续计算。

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

不叫linearize。计算被暂停，直到processSteps调用getNext()。

使用延续到二进制递归转换为尾递归

相关推荐