Recursion, Laziness & Tail Calls

@tailrec makes the compiler fail if the call isn't in tail position.

30.1 @tailrec

@tailrec makes the compiler fail if the call isn't in tail position. The JVM has no general TCO, so only self-recursive tail calls are optimized (to loops).

import scala.annotation.tailrec

def factorial(n: Int): BigInt =
  @tailrec def go(n: Int, acc: BigInt): BigInt =
    if n <= 1 then acc else go(n - 1, acc * n)
  go(n, 1)

30.2 Trampolining for mutual recursion

Effect libraries (cats.Eval, IO, ZIO) are stack-safe trampolines.

import scala.util.control.TailCalls.*

def isEven(n: Int): TailRec[Boolean] = if n == 0 then done(true) else tailcall(isOdd(n - 1))
def isOdd(n: Int): TailRec[Boolean] = if n == 0 then done(false) else tailcall(isEven(n - 1))

isEven(1_000_000).result

30.3 Laziness tools

lazy val — computed once on first access (thread-safe).

By-name parameters => A.

LazyList, view, Iterator.

cats.Eval — Eval.now, Eval.later, Eval.always, stack-safe flatMap.

30.4 Memoization

import scala.collection.mutable
def memoize[A, B](f: A => B): A => B =
  val cache = mutable.HashMap.empty[A, B]
  a => cache.getOrElseUpdate(a, f(a))

lazy val fib: Int => BigInt = memoize {
  case 0 => 0
  case 1 => 1
  case n => fib(n - 1) + fib(n - 2)
}