Scala Language Recursion Stackless recursion with trampoline(scala.util.control.TailCalls)
Example
It is very common to get a StackOverflowError error while calling recursive function. Scala standard library offers TailCall to avoid stack overflow by using heap objects and continuations to store the local state of the recursion.
Two examples from the scaladoc of TailCalls
import scala.util.control.TailCalls._
def isEven(xs: List[Int]): TailRec[Boolean] =
if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail))
def isOdd(xs: List[Int]): TailRec[Boolean] =
if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail))
// Does this List contain an even number of elements?
isEven((1 to 100000).toList).result
def fib(n: Int): TailRec[Int] =
if (n < 2) done(n) else for {
x <- tailcall(fib(n - 1))
y <- tailcall(fib(n - 2))
} yield (x + y)
// What is the 40th entry of the Fibonacci series?
fib(40).result
