Newbie Trying To Understand @tailrec annotation


#1

I am curious as to the restrictions for @tailrec annotation in scala. I thought the documentation said that the recursive call has to be the last call in the method and then you are allowed to make the method @tailrec ? I tried it with the method below and I get a syntax error.

@tailrec
private def dfsRecursive(graph: Graph[T], v: T): Unit = {
    marked(v) = true
    /** count each connected vertex **/
    counter += 1
    /** get the adjacent neighbors of v **/
    for (w <- graph.adjreverse(v)) {
    /** if this neigbor has not been seen yet **/
        if (!hasPathTo(w)) {
            edgeTo(w) = v
           /** check the adjacent neighors of w **/
           dfsRecursive(graph, w)
        }
    }
}

Only interested in why the annotation @tailrec does not work here. Another topic can be devoted to the why and how of the method. Not interested in making it purely functional or anything like that.


#2

The function is not tail recursive because of the loop. After a recursive call, the code goes back at the beginning of the loop and continues, so there are actually multiple recursive calls (in general). You’re only tail recursive if you make a single recursive call and it’s the last thing you do.


#3

The recursive call to the function is the return value of the if block, so it has the possibility of not reaching the recursive function call.


#4

thanks … I had a feeling that was the case … but you never know …


#5

Tail call optimization in general works by reusing current stack frame, instead of creating another one. Reusing current stack frame means nothing else than destroying entire local state of fuction (including instruction pointer) and then setting up new function parameters (instruction pointer is set to beginning of function). In order for that to be sound the only allowed actions after a tail call are either nothing or returning a value immediately.

In your example above after recursive call you can have more work to do in current method invocation - that’s why reusing stack frame can’t be done there.

To be clear, a function can have multiple tail calls and still be eligible for full tail call optimization. The only requirement is the one I’ve stated above - after tail call the only allowed work is returning the value immediately.

Because tail call optimization requires returning values immediately functions need some transformation before applying the optimization. E.g: this list reversal is not eligible for tail call optimization:

def reverse[A](list: List[A]): List[A] = {
  list match {
    case x :: xs => reverse(xs) ::: List(x)
    case Nil => Nil
  }
}

After recursive call reverse(xs) we need to concatenate lists - so it breaks the rule of immediately returning a value. We then need to transform it so it can immediately return a value:

def reverse[A](input: List[A]):List[A] = {
  @tailred
  def go(rest: List[A], result: List[A]): List[A] = {
    rest match {
      case head :: tail => go(tail, head :: result)
      case Nil => result
    }
  }
  go(input, Nil)
}

Here you see that after recursive call go(tail, head :: result) the only work to do is to return produced value immediately. Therefore it’s eligible for tail call optimization.

Another important thing in taill call optimization in Scala is that Scala compiler only transforms self-recursive tail calls, i.e. the tail call in a method must call that method itself. Scala compiler can’t optimize e.g. mutual tail calls as in this code:

def methodA(input: T): T = {
  if (condition) methodB(input + 2) else input
}
def methodB(input: T): T = {
  if (condition) methodA(input + 3) else input
}

Scala tail call optimization works by turning a method to a loop, e.g. from that code:

def method(p1: Int, p2: String, p3: Char): String = {
  if (condition(p1)) {
    transform(p2)
  } else {
    if (p3 == 'c') {
      method(p1 + 2, p2, p3)
    } else {
      method(p1, p2, 'a')
    }
  }
}

is turned into that loop:

def method(_p1: Int, _p2: String, _p3: Char): String = {
  // emulate parameter reassignment by copying them to variables first
  var p1 = _p1
  var p2 = _p2
  var p3 = _p3
  while (true) {
    if (condition(p1)) {
      // that's not a recursive call, so just break out of the loop
      return transform(p2)
    } else {
      if (p3 == 'c') {
        // emulate recursive call with new parameters values
        p1 = p1 +2
        p2 = p2
        p3 = p3
        // this is and end of loop body so next iteration will be the same as calling a method recursively
      } else {
        // emulate recursive call with new parameters values
        p1 = p1
        p2 = p2
        p3 = 'a'
        // this is and end of loop body so next iteration will be the same as calling a method recursively
      }
    }
  }
}

I hope that makes it clear. You can always look at bytecode produced by Scala compiler to check what’s going on.


#6

I meant operationally, not syntactically: only one recursive call (at the most) takes place (and it’s the last thing the function does).


#7

Thanks … lots of useful information that would have required who knows how much digging and reading to find out.


#8

How does reusing the stack frame work? Is that a JVM feature, or does the compiler eliminate the method call?


#9

In Java you don’t have access to stack pointers (you can’t manage them directly), so the only thing Scala compiler can do is to eliminate tail calls by converting method body to a loop. That’s why tail calls optimization in Scala is pretty restricted compared to e.g. what C++ can do.

Also JVM doesn’t yet have a built-in tail call optimization. If it had then probably it wouldn’t need special support from Scala compiler. OTOH, I don’t see any special interest in integrating TCO directly in JVM from Java authors.