CODEWITHSUNDEEP
scalarecursiontail-recursion
Omid
Omid

Reputation: 1989

could not optimize @tailrec annotated method loop: it contains a recursive call not in tail position

I have the following recursive function which I want to use tail recursion on it. But compiler complains about my implementation with this error:Error:(79, 7) could not optimize @tailrec annotated method loop: it contains a recursive call not in tail position n match { ^

is it because of for loop that it assumes it's not in tail position?

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)
  }

Upvotes: 2

Views: 1382

Answers (2)

jazmit
jazmit

Reputation: 5410

Yes, that's right. To make it tail recursive, you should use an explicit accumulator which is passed into the recursion.

However, unless you have very deep and narrow trees, you are unlikely to need tail recursive optimization, as the run time will grow very large well before you end up with a stack overflow.

Here's a rough idea of how to make it tail optimized:

@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 =>
  }
}

Upvotes: 3

Bomgar
Bomgar

Reputation: 625

Yes it is because of the loop. The result of a tailrec funtion has to be the result of the recursive call. In your case the result is the result of the for statement.

Upvotes: 0

Related Questions