Based on the code snippets developed in class, summaries and explanations in this document were drafted with the assistance of generative AI. The author verified all facts, revised the text for coherence, and takes full responsibility for the final content.

Week 5 Overview

Week 5 covers option types and tail recursion. Part A works through tail recursion; Part B replaces null with Option and composes optional results.

Part A: 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
}

The tail recursion lecture highlights stack behavior: tail calls can be optimized to avoid growing activation records, which is why tail-recursive formulations are preferred for deep recursion. Choosing among plain recursion, memoization, and tail recursion is a performance and maintainability design decision, and for production systems the tail-recursive form is usually the safer default for large inputs and long-running workloads.

Scala 3 Book pointers: - Recursive functions and control structures: https://docs.scala-lang.org/scala3/book/control-structures.html - @tailrec annotation: https://docs.scala-lang.org/scala3/book/annotations.html

Part B: Option Types

This walkthrough follows the option types lecture: replacing null-style programming with Option, and composing optional results.

1) Baseline: find with null

The first version returns null when no element satisfies the predicate.

def findNull[X](xs: List[X], p: X=>Boolean) : X = xs match
  case Nil => null
  case x :: rest =>
    if p(x) then x
    else findNull(rest, p)
end findNull

This style works, but every use site must remember explicit null checks. That extra burden appears immediately in fallback logic.

2) Fallback search with manual null checks

We search for an element > 5; if missing, we try > 3.

val l = List(1,2,3,4,5)
val r1 = findNull(l, _ > 5)
val r =
  if r1 != null then r1
  else findNull(l, _ > 3)

if r != null then println("Found")
else println("Not found")

The control flow is more error-prone because absence is represented by a raw value (null). Next we encode absence explicitly in the type.

3) Refactor find to return Option

Now absence is None and a successful result is Some(x).

def find[X](xs: List[X], p: X=>Boolean) : Option[X] = xs match
  case Nil => None
  case x :: rest =>
    if p(x) then Some(x)
    else find(rest, p)
end find

This makes the API safer: callers must handle both cases by pattern matching or combinators.

4) Compose searches with orElse

Option allows direct fallback composition without null checks.

find(l, _ > 5) orElse find(l, _ > 3) match
  case None => println("Not found")
  case Some(x) => println(s"Found $x")

The same logic is now concise and explicit about success/failure cases. The following helper shows what orElse means operationally.

5) Explain orElse behavior explicitly

def myOrElse[X](o1: Option[X], o2: Option[X]) =
  o1 match
    case None => o2
    case Some(x) => Some(x)

This reinforces the semantics: keep the first success, otherwise use the fallback.