Tail Recursion

We implement the Fibonacci sequence definition verbatim:

def fib(n: Int) : BigInt =
  require (n >= 0, "Non-negative number expected")
  if n <= 1 then n else fib(n-2) * fib(n-1)
end fib

To measure execution times, we implement a higher-order function that accepts any argumentless function fn, measures its execution time, and forwards its result:

def withTiming[X](fn: () => X) : X =
  val start = System.nanoTime()
  // call a function that is passed as an argument
  val result = fn()
  val d = System.nanoTime() - start
  println(s"Duration ${d/1_000_000} [ms]")
  result
end withTiming

withTiming(() => fib(42))

We identify that its poor exponential runtime complexity is caused by recomputing many intermediate values in the two recursive calls, and ask an LLM to refactor the code so that it memoizes intermediate values:

def fib(n: Int) : BigInt =
  require (n >= 0, "Non-negative number expected")
  val memo = scala.collection.mutable.Map[Int, BigInt]()
  
  def fibMemo(n: Int) : BigInt =
    if memo.contains(n) then memo(n)
    else if n <= 1 then n
    else
      val result = fibMemo(n - 1) + fibMemo(n - 2)
      memo(n) = result
      result
  
  fibMemo(n)
end fib

The runtime performance improves, but runs into StackOverflowError for large values of n. The reason is that we still cause a large recursion depth. We refactor the code into tail-recursive form so that the compiler’s tail call optimization is able to rewrite the recursive definition into a loop, which operates on a single activation record rather than pushing new activation records on the stack for each recursive call.

def fibTR(n: Int, a: BigInt = 0, b: BigInt = 1) : BigInt =
  if n == 0 then a
  else if n == 1 then b
  else // fib(n-1) + fib(n-2)
    fibTR(n-1, b, a+b)
end fibTR

An alternative tail-recursive implementation uses LazyList. This implementation combines the memoization of intermediate values with the tail-recursive behavior obtained through lazy evaluation:

val fibLL: LazyList[BigInt] = BigInt(0) #:: BigInt(1) #:: fibLL.zip(fibLL.tail).map {
  case (a, b) => a+b
}