Compiler fooled by mention of recursive function in non-tail position

Question

I'm trying to make an operation on a structure tail recursive by building up a (custom) continuation but the compiler will not accept that my code is tail recursive. As soon as I try and declare a function literal that references the recursive function in the non-tail position it throws an error even if I am not calling the function here. The following is a much distilled dummy example of what triggers the error:

import scala.annotation.tailrec
object Test extends App {
  @tailrec
  def tailrectest(i: Int): Int = i match {
    case i if i > 0 => {
      val x = () => tailrectest(10)
      tailrectest(i - 1)
    }
    case 0 => 0
  }
}

I get

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

It is referring to the line with val x = () => tailrectest(10)

Answer 1

I believe the problem is caused by the fact that when you embed a (recursive) call into a function variable x, the compiler cannot infer in general if it will get called or not (in this simple case it would be possible though). So to be safe, it complains about any recursive call it occurs in the body of the function.

Once you put a recursive call into a variable, the variable can escape from the function (for example being returned by the function, or stored in some global state, etc.) So it can no longer be optimized as a tail-recursive cycle.

Maybe post how you would like to use x so that we can try to find a specific solution.

Answer 2

I totally agree with Petr Pudlák's answer. But for what it's worth, there is a way out: define a helper method to return a wrapper function to tailrectest:

import scala.annotation.tailrec
object Test extends App {
  def tailrectest_ = tailrectest _
  @tailrec
  def tailrectest(i: Int): Int = i match {
    case i if i > 0 => {
      val x = () => tailrectest_(10)
      tailrectest(i - 1)
    }
    case 0 => 0
  }
}

This adds some noise to the code, but at least it works.

However, if what you are trying to do is to build some kind of continuation, your real world code will certainly have to capture some local context in the closure, which precludes my above solution. In this case I don't see an easy way out.

UPDATE (11 march 2013):

Petr Pudlak found a similar but superior solution in another question: http://stackoverflow.com/questions/15334611/how-to-make-a-tail-recusive-method-that-can-also-refer-to-itself-in-a-non-tail-r

By using an inner function, we can actually capture local state, which make it fully usable. Here is his solution, applied to entropyslave's original question:

import scala.annotation.tailrec

object Test extends App {
  def tailrectest(i: Int): Int = {
    @tailrec
    def tailrectestImpl(i: Int): Int = {
      i match {
        case i if i > 0 =>
          val x = () => tailrectest(10)
          tailrectestImpl(i - 1)
        case 0 => 0
      }
    }
    tailrectest( i )
  }
}