F# 树路径列表的尾递归

Question

我想要实现一个递归函数，它接收一棵树并列出它所有的路径。

我的当前实现无法正常工作：

let rec pathToList tree acc =
    match tree with
    | Leaf -> acc
    | Node(leftTree, x, rightTree) ->
        let newPath = x::acc
        pathToList leftTree newPath :: (pathToList rightTree newPath)

由于pathToList leftTree newPath返回的是一个列表而不是一个元素，所以出现了错误。

可以通过使用set来解决这个问题，例如：

let rec pathToList2 t acc =
    match t with
    | Leaf -> Set.singleton acc
    | Node(leftTree, x, rightTree) ->
        let newPath = x::acc
        Set.union (pathToList2 leftTree newPath) (pathToList2 rightTree newPath)

现在，我在使用列表（前者）而不是集合（后者）解决这个问题上有些困惑，你有什么建议可以用尾递归来解决吗？

- user2431438

---

你可以使用@代替Set.union，虽然它可以编译但不是尾递归形式。在这里有一个类似问题的Scheme解决方案，它是尾递归形式的。 - John Palmer

Answer 1

为了解决这个问题，不需要使用@（因为它在第一个列表的长度上是线性的，效率较低），你需要两个累加器：一个用于路径到达父节点（以便可以构建到当前节点的路径），另一个用于迄今为止找到的所有路径（以便可以添加您发现的路径）。

let rec pathToListRec tree pathToParent pathsFound =
    match tree with
    | Leaf -> pathsFound
    | Node (left, x, right) ->
        let pathToHere = x :: pathToParent

        // Add the paths to nodes in the right subtree
        let pathsFound' = pathToListRec right pathToHere pathsFound

        // Add the path to the current node
        let pathsFound'' = pathToHere :: pathsFound'

        // Add the paths to nodes in the left subtree, and return
        pathToListRec left pathToHere pathsFound''

let pathToList1 tree = pathToListRec tree [] []

就尾递归而言，您可以看到上述函数中的两个递归调用之一处于尾位置。然而，仍然有一个在非尾位置上的调用。

对于树处理函数，这里有一个经验法则：你很难让它们完全成为尾递归。原因很简单：如果你天真地去做，至少两个递归之一（向左子树或向右子树）将必然处于非尾位置。唯一的方法是用列表模拟调用堆栈。这意味着您将拥有与非尾递归版本相同的运行时复杂度，只不过您使用的是列表而不是系统提供的调用堆栈，因此速度可能会变慢。

无论如何，以下是它的样子：

let rec pathToListRec stack acc =
    match stack with
    | [] -> acc
    | (pathToParent, tree) :: restStack ->
        match tree with
        | Leaf -> pathToListRec restStack acc
        | Node (left, x, right) ->
            let pathToHere = x :: pathToParent

            // Push both subtrees to the stack
            let newStack = (pathToHere, left) :: (pathToHere, right) :: restStack

            // Add the current path to the result, and keep processing the stack
            pathToListRec newStack (pathToHere :: acc)

// The initial stack just contains the initial tree
let pathToList2 tree = pathToListRec [[], tree] []

这段代码看起来还不错，但是它的执行时间比非尾递归的代码要慢两倍以上，并且分配了更多的内存，因为我们使用列表来完成栈的工作！

> #time;;
--> Timing now on
> for i = 0 to 100000000 do ignore (pathToList1 t);;
Real: 00:00:09.002, CPU: 00:00:09.016, GC gen0: 3815, gen1: 1, gen2: 0
val it : unit = ()
> for i = 0 to 100000000 do ignore (pathToList2 t);;
Real: 00:00:21.882, CPU: 00:00:21.871, GC gen0: 12208, gen1: 3, gen2: 1
val it : unit = ()

总之，当需要进行多次递归调用时，不应过分遵循“将其变为尾递归，就会更快！”的规则，因为这需要以使代码变得更慢的方式进行改变。

- Tarmil

---

在考虑尾递归时，这是一个很好的要点。感谢您的分享。 - GrumpyRodriguez