recursion - 树的路径列表上的 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 返回的不是元素而是列表，因此会出错。

这可以通过设置来解决，例如:

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)

现在，我有点坚持使用列表(以前的)而不是集合(后来的)来解决这个问题，关于如何使用尾递归解决这个问题有什么建议吗？

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 = ()

总结:规则“使其成为尾递归会更快!”当需要进行多次递归调用时，不应遵循极端做法，因为它需要以某种方式更改代码，这会使它变得更慢。