我有以下递归函数,我想对其使用尾递归。但编译器提示我的实现出现以下错误:错误:(79, 7) 无法优化 @tailrec 带注释的方法循环:它包含不在尾部位置的递归调用
n 匹配 {
^
是不是因为for循环,它假设它不在尾部位置?
def dsl[N,E](qNodes:QNodeLike[N,E]*) = {
val markers = scala.collection.mutable.Map.empty[String, N]
@tailrec
def loop(n:QNodeLike[N,E]):Unit = {
n match {
case QNode(head, kids:Seq[HalfEdgeLike[E,N]]) => {
for(kid <- kids){
kid match {
case EmptyHalfEdge() =>
case HalfEdge(e, n) => loop(n)
}
}
}
case QNodeMarker(head, marker, kids:Seq[HalfEdgeLike[E,N]]) => {
markers.update(marker,head)
for(kid <- kids){
kid match {
case EmptyHalfEdge() =>
case HalfEdge(e, n) => loop(n)
}
}
}
}
}
loop(qNodes.head)
}
最佳答案
是的,没错。要使其成为尾递归,您应该使用传递到递归中的显式累加器。
但是,除非您有非常又深又窄的树,否则您不太可能需要尾递归优化,因为在最终导致堆栈溢出之前,运行时间会变得非常长。
以下是如何对其进行尾部优化的粗略想法:
@tailrec
def loop(n:List[QNodeLike[N,E]]):Unit = {
n match {
case QNode(head, kids:Seq[HalfEdgeLike[E,N]]) :: rem => {
kids match {
case Nil =>
case EmptyHalfEdge() :: rem2 => loop(rem2 ::: rem)
case HalfEdge(e, n) :: rem2 => loop(n :: rem2 ::: rem)
}
}
case QNodeMarker(head, marker, kids:Seq[HalfEdgeLike[E,N]]) :: rem => {
markers.update(marker,head)
kids match {
case Nil =>
case EmptyHalfEdge() :: rem2 => loop(rem2 ::: rem)
case HalfEdge(e, n) :: rem2 => loop(n :: rem2 ::: rem)
}
}
case Nil =>
}
}
关于scala - 无法优化@tailrec注释的方法循环: it contains a recursive call not in tail position,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33372871/