The compiler is fooled by the mention of a recursive function in a non-tail position

Question

I am trying to do a tail recursion operation on a structure by creating a (custom) continuation, but the compiler will not accept that my code is tail recursive. As soon as I try to declare a function literal that references a recursive function in a non-tail position, it throws an error even if I don't call the function here. The following is an example of a distilled dummy example of what causes 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 

This applies to a line with val x = () => tailrectest(10)

Answer 1

I believe that the problem is that when embedding a (recursive) call into the function variable x compiler cannot output at all if it is called or not (in this simple case, it will be possible though). To be safe, he complains about any recursive call that he encounters in the function body.

As soon as you put a recursive call into a variable, the variable can exit the function (for example, it is returned by the function or stored in some global state, etc.). Thus, it can no longer be optimized, a recursive loop.

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

Answer 2

I completely agree with the answer of Peter Pudlak. But for what it's worth, there is a way out: Define a helper method to return a wrapper function for 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 build some kind of continuation, your real world code will certainly have to fix some local context in the closure, which excludes my solution above. In this case, I do not see an easy way out.

UPDATE (March 11, 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 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 ) } }