我有这个函数用于在功能上遍历图形:
private def dfs(current: RCell, rCellsMovedWithEdges: Vector[RCell], acc: Vector[RCell] = Vector()): Vector[RCell] = {
current.edges.foldLeft(acc) {
(results, next) =>
if (results.contains(rCellsMovedWithEdges(next))) results
else dfs(rCellsMovedWithEdges(next), rCellsMovedWithEdges, results :+ current)
} :+ current
}
从manuel kiessling here采取的实施
这很好,但我担心最后的“:+ current”会使它非尾递归。
我改成了这个:
private def dfs(current: RCell, rCellsMovedWithEdges: Vector[RCell]): Vector[RCell] = {
@annotation.tailrec
def go(current: RCell, rCellsMovedWithEdges: Vector[RCell], acc: Vector[RCell] = Vector()): Vector[RCell] = {
current.edges.foldLeft(acc) {
(results, next) =>
if (results.contains(rCellsMovedWithEdges(next))) results
else go(rCellsMovedWithEdges(next), rCellsMovedWithEdges, results :+ current)
}
}
go(current, rCellsMovedWithEdges) :+ current
}
但编译器说递归调用不在尾部位置。
每次机会左移是否已经尾递归?
如果没有,还有另一种方法可以做我想要的吗?
这不是尾递归,因为最后的调用不是go
,而是foldLeft
。由于foldLeft
多次调用go
,因此它无法进行相互尾递归。由于递归算法在很大程度上依赖于调用堆栈来跟踪您在树中的位置,因此很难使DFS尾递归。如果你能保证你的树很浅,我建议你不要打扰。否则,您将需要传递一个显式堆栈(List
在这里是一个不错的选择)并完全重写您的代码。
如果要以递归方式实现DFS,则必须基本上手动管理堆栈:
def dfs(start: RCell, rCellsMovedWithEdges: Vector[RCell]): Vector[RCell] = {
@annotation.tailrec
def go(stack: List[RCell], visited: Set[RCell], acc: Vector[RCell]): Vector[RCell] = stack match {
case Nil => acc
case head :: rest => {
if (visited.contains(head)) {
go(rest, visited, acc)
} else {
val expanded = head.edges.map(rCellsMovedWithEdges)
val unvisited = expanded.filterNot(visited.contains)
go(unvisited ++ rest, visited + head, acc :+ head)
}
}
}
go(List(start), Set.empty, Vector.empty)
}
额外奖励:将unvisited ++ rest
改为rest ++ unvisited
并获得BFS。