CODEWITHSUNDEEP
scalatail-recursiontail-call-optimization
Rouzbeh Delavari
Rouzbeh Delavari

Reputation: 179

How can I annotate this tail recursive Scala function

I have a function that i know is tail recursive. But because of the way I define it, the compiler complains about the function having a recursive call in non tail position. This is the function.

@tailrec
def travel: (Int, List[Char]) => Int = {
    case (n,        Nil) => n
    case (n, '~' :: sls) => travel(0, sls)
    case (n, '^' :: sls) => travel(max(n-1,0), sls)
    case (n, '>' :: sls) => travel(n+1, sls)
    case (_,  s  :: sls) => throw new IllegalArgumentException("Illegal selector '" + s + "'")
}

I get

error: could not optimize @tailrec annotated method travel: it contains a recursive call not in tail position
def travel: (Int, List[Char]) => Int = {

If I write it as this, it works fine.

@tailrec
def travel(n:Int, l:List[Char]): Int = (n,l) match {
    case (n,        Nil) => n
    case (n, '~' :: sls) => travel(0, sls)
    case (n, '^' :: sls) => travel(max(n-1,0), sls)
    case (n, '>' :: sls) => travel(n+1, sls)
    case (_,  s  :: sls) => throw new IllegalArgumentException("Illegal selector '" + s + "'")
}

I think it has something to do with the def: (Input) => Output = {} type declaration style. I use it because it looks cleaner than writing nested matches, or a match on a tuple.

Upvotes: 2

Views: 514

Answers (1)

Rex Kerr
Rex Kerr

Reputation: 167901

The two are not the same. In the first case, the method produces a function that then calls the method again (that produces a function, etc.). That is, you're creating a new instance of Function1[(Int, List[Char]), Int] each time you call travel in the first case. Unsurprisingly, this cannot be converted into a jump instruction. (In theory one could, but the analysis would be quite complicated, as one would have to un-do all those object creations.)

In the second case, it's just a method calling itself, which can be converted into a jump.

Upvotes: 7

Related Questions