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

结论：“做它尾递归它会更快！当需要进行多次递归调用时，不应该遵循极端情况，因为它要求以更慢的方式更改代码。