在递归函数中进行记忆

使用前面计算整数的阶乘的示例，在散列表中放入在递归内计算的所有阶乘的值，这些值不会出现在表中。

由于有关的文章在记忆化 ，我们定义一个函数 f 接受一个函数参数 fact 和整数参数。此函数 f 包含从 fact(n-1) 计算 n 的阶乘的指令。

这允许通过 memorec 而不是 fact 本身返回的函数来处理递归，并且如果 fact(n-1) 值已经被计算并且位于散列表中，则可能停止计算。

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

结果：

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