Scalan epäintuitiivinen häntärekursio

Scalaa pidetään funktionaalisena ohjelmointikielenä, mutta sen tuki häntärekursille (tail recursion) on yllättävän rajoittunut. Tämä johtuu yksinkertaisesti siitä, että Java VM:n nykyinen versio ei tue häntärekursiota ollenkaan.

Kuten tämä artikkeli selittää, Scalan metodit toimivat häntärekursiivisesti ainoastaan jos ne on määritelty final-tyyppiseksi. Tällöin Scala pystyy optimoimaan ne while-loopiksi. Muussa tapauksessa metodikutsut luovat aina uuden stack framen siltä varalta, että itseään kutsuva metodi onkin overridattu jossakin perityssä luokassa.

Väärin:

class Generator {
  def generate(l: Long): Long = {
    if (l > 1000000) return l
    generate(l+1)
  }
}

scala> new Generator().generate(0)
java.lang.StackOverflowError
	at Generator.generate(<console>:4...

Oikein:

class Generator {
  final def generate(l: Long): Long = {
    if (l > 1000000) return l
    generate(l+1)
  }
}

scala> new Generator().generate(0)
res0: Long = 1000001

Object-luokkien metodit ovat automaattisesti final-tyyppisiä:

object Generator {
  def generate(l: Long): Long = {
    if (l > 1000000) return l
    generate(l+1)
  }
}

scala> Generator.generate(0)
res0: Long = 1000001