recur.scala

import scala.annotation.tailrec

sealed abstract class Var {

  def walk(subst: Subst): Var = {
    @tailrec
    def go(v: Var, stack: List[Var], acc: Option[Var]): Var =
      v match {
        case Unbound(k) =>
          subst.get(k) match {
            case None => acc.fold(v)(u => Cons(u, v))
            case Some(v) => go(v, stack, acc)
          }
        case Cons(h, t) =>
          go(h, t :: stack, acc)
        case _ =>
          stack match {
            case Nil => acc.fold(v)(u => Cons(u, v))
            case x :: xs => go(x, xs, acc.map(u => Cons(u, v)).orElse(Some(v)))
          }
      }
    go(this, Nil, None)
  }

}

case class Bound(value: Any) extends Var

case class Unbound(id: Long) extends Var

case class Cons(head: Var, tail: Var) extends Var

def walk(subst: Subst): Var = {
    //@tailrec                                                                                                                                                                                                     
    def go(v: Var, cont: Var => Var): Var =
      v match {
        case Unbound(k) =>
          subst.get(k) match {
            case None => cont(v)
            case Some(v) => go(v, cont)
          }
        case Cons(h, t) => go(h, h => go(t, t => cont(Cons(h, t))))
        case _ => cont(v)
      }
    go(this, v => v)
  }

trait Subst { def get(v: Long): Option[Var] }

type GoType = (Var, (Var => Var)) => Var
def fix(f: GoType => GoType)(v: Var, cont: Var => Var): Var = {
  f(fix(f))(v, cont)
}

def walk(subst: Subst): Var = {
  @scala.annotation.tailrec
  def go(self: (Var, (Var => Var)) => Var)(v: Var, cont: Var => Var): Var = {
    v match {
      case Unbound(k) =>
        subst.get(k) match {
          case None => cont(v)
          case Some(v) => go(self)(v, cont)
        }
      case Cons(h, t) => go(self)(h, h => self(t, t => Cons(h, t)))
      case _ => cont(v)
    }
  }

  fix(go)(this, Id)
}

      case Cons(h, t) => go(self)(h, h => self(t, t => Cons(h, t)))

継続内の self は普通にメソッド呼び出しするのでスタック深くなっちゃうけど、そんな大量に Cons ないでしょ、というつもりで、とりあえず他の箇所は goto になるようにコンパイラを言いくるめました。
Cons だらけだと普通にスタックあふれます。