使用 trampoline 進行無堆疊遞迴（scala.util.control.TailCalls）

在呼叫遞迴函式時，通常會發生 StackOverflowError 錯誤。Scala 標準庫提供 TailCall， 以通過使用堆物件和 continuation 來儲存遞迴的本地狀態來避免堆疊溢位。

來自 TailCalls 的 scaladoc 的兩個例子

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