CODEWITHSUNDEEP
scalatail-recursion
ayvango
ayvango

Reputation: 5977

How to ensure tail recursion consistently

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.

Upvotes: 1

Views: 274

Answers (2)

Todd
Todd

Reputation: 31660

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

Upvotes: 2

blintend
blintend

Reputation: 368

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.

Upvotes: 3

Related Questions