Scala: expanded syntax of trampolining function breaks tail recursion

This is an exercise in "Functional Programming in Scala," chapter 13, to implement a trampoline for interpreting tail-recursive functions.

runTrampoline2 is not tail-recursive, and overflows the stack with my test inputs. Furthermore, the tailrec annotation gives a compiler error for runTrampoline2. runTrampoline is tail-recursive and passes the annotation's compile-time check.

My best bet is that the difference between these two trampolines lies in the way a val captures, or doesn't capture, a Unit, like here:

scala> val foo = println("abc")
val foo = println("abc")
abc
foo: Unit = ()

scala> foo
foo

scala> val bar: Int = {println("xyz"); 5}
val bar: Int = {println("xyz"); 5}
xyz
bar: Int = 5

scala> bar
bar
res8: Int = 5

Otherwise these two trampolines look identical to me. I'll include the code for the Free monad and the Suspend, Return, and FlatMap constructors if someone comments they are important for this question, but I don't think they are. Is runTrampoline2's tail-recursion broken by a side effect leaking out of the vals? Thanks!

@annotation.tailrec
def runTrampoline[A](tra: Free[Function0,A]): A =
  tra match {
    // case Return(A)
    case Return(a1) => a1
    // case Suspend(Function0[A])
    case Suspend(function0A1) => function0A1()
    // case FlatMap(Free[Function0[_],A], A=>Free[Function0,B]]
    case FlatMap(free1, aFree2) => free1 match {
      // case Return(A)
      case Return(a2) => runTrampoline(aFree2(a2))
      // case Suspend(Function0[A])
      case Suspend(function0A) => runTrampoline(aFree2(function0A()))
      // case FlatMap(Free[Function0[_],A], A=>Free[Function0,B]]
      case FlatMap(a0,g) =>
        runTrampoline {
          a0 flatMap { a0 => g(a0) flatMap aFree2 }
        }
    }
  }


//@annotation.tailrec
def runTrampoline2[A](tra: Free[Function0,A]): A =
  tra match {
    // case Return(A)
    case Return(a1) => a1
    // case Suspend(Function0[A])
    case Suspend(function0A1) => {
      val a1: A = function0A1()
      a1
    }
    // case FlatMap(Free[Function0[_],A], A=>Free[Function0,A]]
    case FlatMap(free1, aFree2) => free1 match {
      // case Return(A)
      case Return(a2) => {
        val free2: Free[Function0,A] = aFree2(a2)
        val a3: A = runTrampoline2(free2)
        a3
      }
      // case Suspend(Function0[A])
      case Suspend(function0A) => {
        val a2: A = function0A()
        val free2: Free[Function0,A] = aFree2(a2)
        val a3: A = runTrampoline2(free2)
        a3
      }
      // case FlatMap(Free[Function0[_],A], A=>Free[Function0,B]]
      case FlatMap(a0,g) =>
        runTrampoline2 {
          a0 flatMap { a0 => g(a0) flatMap aFree2 }
        }
      }
      }

I asked a similar question a month ago, about type annotations breaking tail-recursion: Scala: type annotations make tail recursion check fail

---

Solved by Aivean. Here is a corrected version of the trampoline. Each recursive call is at the very end of the case containing it.

@annotation.tailrec
def runTrampoline3[A](tra: Free[Function0,A]): A =
  tra match {
    case Return(a1) => a1
    case Suspend(function0A1) => {
      val a1 = function0A1()
      a1
    }
    case FlatMap(free1, aFree2) => free1 match {
      case Return(a2) => {
        val free2 = aFree2(a2)
        runTrampoline3(free2)
      }
      case Suspend(function0A) => {
        val a2 = function0A()
        val free2 = aFree2(a2)
        runTrampoline3(free2)
      }
      case FlatMap(a0,g) =>
        runTrampoline3 {
          a0 flatMap { a0 => g(a0) flatMap aFree2 }
        }
     }
  }

It appears that Scala compiler recognizes tail recursion only when call to itself is actually the last operation in the function.

I decompiled two different examples to check this.

Tail recursion:

scala:

def rec:Int = rec

java:

public final class _$$anon$1 {
  private int rec() {
    while (true) {}
  }
}

No tail recursion:

scala:

def rec:Int = {
  val i = rec
  i
}

java:

public final class _$$anon$1 {
  private int rec() {
    final int i = this.rec();
    return i;
  }
}