1

In the below code - quite trivial max and sum of lists - I have a recursive function called at the end of a method. Will the scala compiler treat this as tail recursive and optimize the stack frame usage? How do I know/how can I verify this?

package example

import common._

object Lists {
  def sum(xs: List[Int]): Int = {

    def recSum(current: Int, remaining: List[Int]): Int = {
      if (remaining.isEmpty) current else recSum(current + remaining.head, remaining.drop(1))
    } 

    recSum(0, xs)
  }

  def max(xs: List[Int]): Int = {

    def recMax(current: Int, remaining: List[Int], firstIteration: Boolean): Int = {
      if(remaining.isEmpty){
        current
      }else{
        val newMax = if (firstIteration || remaining.head>current) remaining.head else current
        recMax(newMax, remaining.drop(1), false)
      }
    }

    if (xs.isEmpty) throw new NoSuchElementException else recMax(0, xs, true)
  }
}
JasonG
  • 5,794
  • 4
  • 39
  • 67
  • possible duplicate of [What is the Scala annotation to ensure a tail recursive function is optimized?](http://stackoverflow.com/questions/3114142/what-is-the-scala-annotation-to-ensure-a-tail-recursive-function-is-optimized) – om-nom-nom Mar 29 '13 at 19:34

1 Answers1

4

Add @tailrec before function definition to make the compiler cause an error on non-tailrecursive methods :) Also, you have to assume the function will be as efficient as an imperative loop (aka. for/while loop) when you have it optimized in this way by the compiler.

Felix
  • 8,385
  • 10
  • 40
  • 59