scala/ScalaBook/chapter-03/memo3.scala

class Memo1[-α, +β](f: α => β) extends (α => β) {
  import scala.collection.mutable
  private[this] val vals = mutable.Map.empty[α, β]

  def apply(x: α): β = {
    if (vals.contains(x)) {
      vals(x)
    }
    else {
      val y = f(x)
      vals + ((x, y))
      y
    }
  }
}

object Memo1 {
  def apply[α, β](f: α => β) = new Memo1(f)
  def Y[α, β](f: (α, α => β) => β) = {
    var yf: α => β = null
    yf = Memo1(f(_, yf(_)))
    yf
  }
}

def facRec(n: BigInt, f: BigInt => BigInt): BigInt = {
  if (n == 0) 1
  else n*f(n - 1)
}

val fac = Memo1.Y(facRec)

for (k <- 5 to 0 by -1)
  println(fac(k))