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

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

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