cached recursion function for Scala, it's performance comparison with Y combinator for calculating fibonacci numbers

cached recursion

  def cachedRec[A, B](rec: (A => B) => (A => B)): A => CachedRecResult[A, B] = {
    val cache = mutable.HashMap.empty[A, B]
    // fixed-point combinator
    def YY(f: (A => B) => (A => B)): A => B = {
      a => cache.getOrElse(a, {
        val b = rec(YY(rec))(a)
        cache += a -> b
        b
      })
    }
    YY(rec) andThen (res => CachedRecResult(res, cache.toMap))
  }

  case class CachedRecResult[A, B](result: B, cache: Map[A, B])

  // let's compare it's performance with Y's

  def Y[A, B](rec: (A => B) => (A => B)): A => B = rec(Y(rec))(_: A)

  val fib: (Long => Long) => (Long => Long) = rec => {
    case 1|2 => 1
    case i => rec(i-1) + rec(i-2)
  }

  def elapsed[R](f: => R) = {
    val time1 = System.nanoTime()
    val res = f
    val time2 = System.nanoTime()
    res -> (time2-time1)
  }

  // let's see performance calculating 10th fibonacci number
  elapsed(Y(fib)(10)) // (55,33214)
  elapsed(cachedRec(fib)(10)) // (CachedRecResult(55,Map(...)),257276)
  // well, the cached one took 7 times longer, but let's see for fib(50)
  elapsed(Y(fib)(50)) // (12586269025,256037847273)
  elapsed(cachedRec(fib)(50)) // (CachedRecResult(12586269025,Map(...)), 1741272)
  // the cached one did it roughly 147040 times faster