scala/ScalaBook/chapter-03/memo2.scala

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

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

object Memo1 {
  def apply[T, R](f: T => R) = new Memo1(f)
  def Y[T, R](f: (T, T => R) => R) = {
    def yf: T => R = 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))