我有这个函数来函数遍历图形:
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
}
此处的实现取自曼努埃尔·基斯林
这很好,但我担心最后的":+ 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。