gistfile1.txt

$ scala TrampolineTest.scala
Calculating fib(1). Max stack size: 0
Calculating fib(2). Max stack size: 1
Calculating fib(3). Max stack size: 2
Calculating fib(4). Max stack size: 3
Calculating fib(5). Max stack size: 4
Calculating fib(6). Max stack size: 5
Calculating fib(7). Max stack size: 6
Calculating fib(8). Max stack size: 7
Calculating fib(9). Max stack size: 8
Calculating fib(10). Max stack size: 9
Calculating fib(11). Max stack size: 10
Calculating fib(12). Max stack size: 11
Calculating fib(13). Max stack size: 12
Calculating fib(14). Max stack size: 13
Calculating fib(15). Max stack size: 14
Calculating fib(16). Max stack size: 15
Calculating fib(17). Max stack size: 16
Calculating fib(18). Max stack size: 17
Calculating fib(19). Max stack size: 18
Calculating fib(20). Max stack size: 19
Calculating fib(21). Max stack size: 20
Calculating fib(22). Max stack size: 21
Calculating fib(23). Max stack size: 22
Calculating fib(24). Max stack size: 23
Calculating fib(25). Max stack size: 24
Calculating fib(26). Max stack size: 25
Calculating fib(27). Max stack size: 26
Calculating fib(28). Max stack size: 27
Calculating fib(29). Max stack size: 28

TrampolineTest.scala

sealed trait Trampoline[A] {
  def map[B](f: A => B): Trampoline[B] =
    flatMap(a => More(() => Done(f(a))))
  def flatMap[B](f: A => Trampoline[B]): Trampoline[B] =
    Cont(this, f)
  def run: A = {
    var cur: Trampoline[_] = this
    var stack: List[Any => Trampoline[A]] = List()
    var maxStackSize = 0 // NEW
    var result: Option[A] = None
    while (result.isEmpty) {
      cur match {
        case Done(a) => stack match {
          case Nil => result = Some(a.asInstanceOf[A])
          case c :: cs => {
            cur = c(a)
            stack = cs
          }
        }
        case More(t) => cur = t()
        case Cont(a, f) => {
          cur = a
          stack = f.asInstanceOf[Any => Trampoline[A]] :: stack
        }
      }
      if (maxStackSize < stack.size) maxStackSize = stack.size // NEW
    }
    println("Max stack size: " + maxStackSize) // NEW
    result.get
  }
}
case class Done[A](a: A) extends Trampoline[A]
case class More[A](a: () => Trampoline[A]) extends Trampoline[A]
case class Cont[A, B](a: Trampoline[A],
                      f: A => Trampoline[B]) extends Trampoline[B]

def fib(n: Int): Trampoline[Int] =
  if (n < 2) Done(n) else for {
    x <- fib(n - 1)
    y <- fib(n - 2)
  } yield (x + y)

for (n <- 1 until 30) {
  print(s"Calculating fib($n). ")
  fib(n).run
}