How to ensure tail recursion consistently

Question

I'd like to make some function be optimized for tail-recursion. The function would emit stackoverflow exception without optimization.

Sample code:

import scala.util.Try
import scala.annotation.tailrec

object Main {
  val trials = 10

  @tailrec
  val gcd : (Int, Int) => Int = {
    case (a,b) if (a == b) => a
    case (a,b) if (a > b) => gcd (a-b,b)
    case (a,b) if (b > a) => gcd (a, b-a)
  }

  def main(args : Array[String]) : Unit = {
    testTailRec()
  }

  def testTailRec() {
    val outputs : List[Boolean] = Range(0, trials).toList.map(_ + 6000) map { x =>
      Try( gcd(x, 1) ).toOption.isDefined
    }
    outputTestResult(outputs)
  }

  def outputTestResult(source : List[Boolean]) = {
    val failed = source.count(_ == false)
    val initial = source.takeWhile(_ == false).length
    println( s"totally $failed failures, $initial of which at the beginning")
  }
}

Running it will produce the following output:

[info] Running Main 
[info] totally 2 failures, 2 of which at the beginning

So, first two runs are performed without optimization and are dropped half-way due to the stackoveflow exception, and only later invocations produce desired result.

There is a workaround: you need to warm up the function with fake runs before actually utilizing it. But it seems clumsy and highly inconvenient. Are there any other means to ensure my recursive function would be optimized for tail recursion before it runs for first time?

update:

I was told to use two-step definition

@tailrec
def gcd_worker(a: Int, b: Int): Int = {
      if (a == b) a
      else if (a > b) gcd(a-b,b)
         else gcd(a, b-a)
}
val gcd : (Int,Int) => Int = gcd_worker(_,_)

I prefer to keep clean functional-style definition if it is possible.

I wonder if this would help. Explicitly setting a larger stack size. See http://stackoverflow.com/questions/20030120/java-default-stack-size and http://stackoverflow.com/questions/3700459/how-to-increase-the-java-stack-size — Mike Meinz, Jul 22 '14 at 16:26
This would not help. Just replace 6000 with a larger constant and you would still get the same problem. Tail recursion optimization converts recursion into iteration. And I seek for this — ayvango, Jul 22 '14 at 16:31
FWIW, `val foo = { def f = ??? ; f }` is a common idiom. BTW, tailrec is compile-time, but you seem to be talking about runtime compilations, tl;dr. — som-snytt, Jul 23 '14 at 02:43

score 3 · Accepted Answer · answered Jul 22 '14 at 17:09

3

I do not think @tailrec applies to the function defined as val at all. Change it to a def and it will run without errors.

answered Jul 22 '14 at 17:09

blintend

368
2
7

1

true. And since I find this very confusing I filed a ticked here: https://issues.scala-lang.org/browse/SI-8742 It should definitely be explicit – Gabriele Petronella Jul 22 '14 at 17:35

score 2 · Answer 2 · answered Jul 22 '14 at 17:10

From what I understand @tailrec[1] needs to be on a method, not a field. I was able to get this to be tail recursive in the REPL by making the following change:

@tailrec
def gcd(a: Int, b: Int): Int = {
      if (a == b) a
      else if (a > b) gcd(a-b,b)
      else gcd(a, b-a)
}

[1] http://www.scala-lang.org/api/current/index.html#scala.annotation.tailrec

How to ensure tail recursion consistently

update:

2 Answers2