TrampolineFibonacci.scala

// See also: http://blog.higher-order.com/assets/trampolines.pdf

// Not stack-safe

def fib(n: Int): Int =
  if n <= 1 then n
  else fib(n - 1) + fib(n - 2)

fib(10)
// res0: Int = 55

// Stack-safe

sealed trait Trampoline[A]:
  def map[B](f: A => B): Trampoline[B] = flatMap(f andThen (Done(_)))
  def flatMap[B](f: A => Trampoline[B]): Trampoline[B] = FlatMap(this, f)

sealed case class Done[A](value: A) extends Trampoline[A]
sealed case class Next[A](step: () => Trampoline[A]) extends Trampoline[A]
sealed case class FlatMap[A, B](a: Trampoline[A], f: A => Trampoline[B]) extends Trampoline[B]

def run[A](computation: Trampoline[A]): A =
  computation match
    case Done(value)   => value
    case Next(step)    => run(step())
    case FlatMap(a, f) =>
      a match
        case Done(value)   => run(f(value))
        case Next(step)    => run(FlatMap(step(), f))
        case FlatMap(b, g) => run(b.flatMap(bb => g(bb).flatMap(f)))

val fourtytwo = (Next(() => Next(() => Done(7))))
// fourtytwo: Next[Int] = Next(repl.MdocSession$MdocApp$$Lambda$13756/0x0000000103755040@7b8e3729)
run(fourtytwo)
// res1: Int = 7

def trampolineFib(n: Int): Trampoline[Int] =
  if (n <= 1) Done(n)
  else
    FlatMap[Int, Int](
      Next(() => trampolineFib(n - 1)),
      i => FlatMap[Int, Int](Next(() => trampolineFib(n - 2)), j => Done(i + j))
    )

trampolineFib(10)
// res2: Trampoline[Int] = FlatMap(Next(repl.MdocSession$MdocApp$$Lambda$13758/0x0000000103754040@60b06b4d),repl.MdocSession$MdocApp$$Lambda$13759/0x0000000103753840@1767b077)
run(trampolineFib(10))
// res3: Int = 55