I'll speak generally, then. About recursive functions using a cache: they must return, in addition of the result, an upated cache.

cache-recursive.scala

/**
 * https://class.coursera.org/progfun-002/forum/thread?thread_id=1175#comment-3124
 **/
object Main extends App {
  class MemoStringFunction[T](f: String => T, base: String) {
    private lazy val v = f(base)

    private lazy val ts = (for {
        tx <- 'a' to 'z'
      } yield (tx, new MemoStringFunction(f, base  + tx))).toMap

    private def get(x: String): T = x match {
      case "" => v
      case s => ts(s.head).get(s.tail)
    }

    def apply(x: String): T = get(x)
  }

  val f = new MemoStringFunction(s => { println("bork."); s.length }, "")

  println(f("a"))
  println(f("abcdef"))
  println(f("a"))
  println(f("abcdef"))
}