Which recursive calls are optimized by Scala complier, so they run just as quickly as hand-optimized versions that use while loops?
Explanation
Get an explanation when it's available:
Theory
  • Scala optimizes the tail recursive call:
    def bang(x: Int): Int = 
      if (x == 0) throw new Exception("bang!")
      else bang(x - 1)
    scala> bang(5)
    java.lang.Exception: bang!
          at .bang(<console>:5)
          at .<init>(<console>:6)
    Scala only optimizes directly recursive calls back to the same function making the call. If the recursion is indirect, no optimization is possible:
    def isEven(x: Int): Boolean =
      if (x == 0) true else isOdd(x - 1)
    def isOdd(x: Int): Boolean =
      if (x == 0) false else isEven(x - 1)
    You also won't get a tail-call optimization if the final call goes to a function value.
    val funValue = nestedFun _
    def nestedFun(x: Int) { 
      if (x != 0) { println(x); funValue(x - 1) }
    }
    Read more: Tail recursion

Follow CodeGalaxy

Mobile Beta

Get it on Google Play
Send Feedback
Cosmo
Sign Up Now
or Subscribe for future quizzes