Combine memoization and tail-recursion

Viewed 4663

Is it possible to combine memoization and tail-recursion somehow? I'm learning F# at the moment and understand both concepts but can't seem to combine them.

Suppose I have the following memoize function (from Real-World Functional Programming):

let memoize f = let cache = new Dictionary<_, _>()
                (fun x -> match cache.TryGetValue(x) with
                          | true, y -> y
                          | _       -> let v = f(x)
                                       cache.Add(x, v)
                                       v)

and the following factorial function:

let rec factorial(x) = if (x = 0) then 1 else x * factorial(x - 1)

Memoizing factorial isn't too difficult and making it tail-recursive isn't either:

let rec memoizedFactorial =
  memoize (fun x -> if (x = 0) then 1 else x * memoizedFactorial(x - 1))

let tailRecursiveFactorial(x) =
  let rec factorialUtil(x, res) = if (x = 0)
                                  then res
                                  else let newRes = x * res
                                       factorialUtil(x - 1, newRes)
  factorialUtil(x, 1)

But can you combine memoization and tail-recursion? I made some attempts but can't seem to get it working. Or is this simply not possible?

5 Answers
Related