F# Memoization Memoization in a recursive function
Example
Using the previous example of calculating the factorial of an integer, put in the hash table all values of factorial calculated inside the recursion, that do not appear in the table.
As in the article about memoization, we declare a function f that accepts a function parameter fact and a integer parameter. This function f, includes instructions to calculate the factorial of n from fact(n-1).
This allows to handle recursion by the function returned by memorec and not by fact itself and possibly stop the calculation if the fact(n-1) value has been already calculated and is located in the hash table.
let memorec f =
let cache = Dictionary<_,_>()
let rec frec n =
let value = ref 0
let exist = cache.TryGetValue(n, value)
match exist with
| true ->
printfn "%O -> In cache" n
| false ->
printfn "%O -> Not in cache, calling function..." n
value := f frec n
cache.Add(n, !value)
!value
in frec
let f = fun fact n -> if n<2 then 1 else n*fact(n-1)
[<EntryPoint>]
let main argv =
let g = memorec(f)
printfn "%A" (g 10)
printfn "%A" "---------------------"
printfn "%A" (g 5)
Console.ReadLine()
0
Result:
10 -> Not in cache, calling function...
9 -> Not in cache, calling function...
8 -> Not in cache, calling function...
7 -> Not in cache, calling function...
6 -> Not in cache, calling function...
5 -> Not in cache, calling function...
4 -> Not in cache, calling function...
3 -> Not in cache, calling function...
2 -> Not in cache, calling function...
1 -> Not in cache, calling function...
3628800
"---------------------"
5 -> In cache
120
