我有以下递归函数,我想对它使用尾递归。但是编译器抱怨我的实现有这个错误:Error:(79, 7) could not optimize @tailrec annotated method loop: it contains a recursive call not in tail position
n match {
^
是因为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 =>
}
}
是的,这是因为循环。尾函数的结果必须是递归调用的结果。在您的示例中,结果是for语句的结果。