recursion - 我怎样才能使这个函数成为尾递归的？

Question

我是 still尝试实现 2-3 个手指树，我取得了很好的进展(repository)。在做一些基准测试时，我发现当树相当大时，我非常基本的 toList 会导致 StackOverflowException。起初，我看到了一个简单的修复方法，并将其设为尾递归。

不幸的是，事实证明 toList 不是罪魁祸首，但 viewr 是:

/// Return both the right-most element and the remaining tree (lazily).
let rec viewr<'a> : FingerTree<'a> -> View<'a> = function
    | Empty -> Nil
    | Single x -> View(x, lazyval Empty)
    | Deep(prefix, deeper, One x) ->
        let rest = lazy (
            match viewr deeper.Value with
            | Nil ->
                prefix |> Digit.promote
            | View (node, lazyRest) ->
                let suffix = node |> Node.toList |> Digit.ofList
                Deep(prefix, lazyRest, suffix)
        )
        View(x, rest)
    | Deep(prefix, deeper, Digit.SplitLast(shorter, x)) ->
        View(x, lazy Deep(prefix, deeper, shorter))
    | _ -> failwith Messages.patternMatchImpossible

寻找唯一的递归调用很明显这不是尾递归。不知怎的，我希望这个问题不会存在，因为那个调用被包装在 Lazy 中，恕我直言，它类似于一个延续。

我听说过和读过延续，但到目前为止从未(不得不)使用(d)它们。我想在这里我真的需要。我盯着代码看了很长一段时间，到处放函数参数，在其他地方调用它们……我完全迷路了!

如何做到这一点？

---

更新:调用代码如下所示:

/// Convert a tree to a list (left to right).
let toList tree =
    let rec toList acc tree =
        match viewr tree with
        | Nil -> acc
        | View(head, Lazy tail) -> tail |> toList (head::acc)
    toList [] tree

---

更新2:导致崩溃的代码是这个。

let tree = seq {1..200000} |> ConcatDeque.ofSeq
let back = tree |> ConcatDeque.toList

这棵树建得很好，我检查了一下，它只有 12 层深。是第 2 行中的调用触发了溢出。

---

更新 3: kvb是的，那个pipe issue我之前遇到的跟这个有关系。重新测试调试/发布和使用/不使用管道的交叉产品，它在所有情况下都有效，但只有一种情况:管道运算符(operator)崩溃的 Debug模式。 32 位和 64 位的行为相同。

我很确定我在发布问题时正在运行 Release模式，但今天它正在运行。也许还有其他一些因素……对此感到抱歉。

---

尽管崩溃已解决，但出于理论上的兴趣，我将问题悬而未决。毕竟，我们是来学习的，不是吗？

所以让我调整一下这个问题:
从代码来看，viewr肯定不是尾递归的。为什么它不会总是爆炸，如何使用延续来重写它？

Answer 1

调用 viewr 永远不会导致对 viewr 的立即递归调用(递归调用受 lazy 保护，并且不会在余数中强制执行对 viewr 的调用)，因此无需使其尾递归以防止堆栈无限增长。也就是说，对 viewr 的调用会创建一个新的堆栈帧，然后在 viewr 的工作完成时立即将其弹出；然后，调用者可以强制延迟值，从而为嵌套的 viewr 调用生成新的堆栈帧，然后立即再次弹出，等等，因此重复此过程不会导致堆栈溢出。