我不确定是否有更简单的方法可以做到这一点，但一种方法是创建一个记忆 y 组合器：
let memoY f =
let cache = Dictionary<_,_>()
let rec fn x =
match cache.TryGetValue(x) with
| true,y -> y
| _ -> let v = f fn x
cache.Add(x,v)
v
fn
然后，您可以使用此组合器代替“let rec”，第一个参数表示要递归调用的函数：
let tailRecFact =
let factHelper fact (x, res) =
printfn "%i,%i" x res
if x = 0 then res
else fact (x-1, x*res)
let memoized = memoY factHelper
fun x -> memoized (x,1)
编辑
正如 Mitya 指出的那样，memoY它不保留备忘录的尾递归属性。这是一个修改后的组合器，它使用异常和可变状态来记忆任何递归函数而不会溢出堆栈（即使原始函数本身不是尾递归的！）：
let memoY f =
let cache = Dictionary<_,_>()
fun x ->
let l = ResizeArray([x])
while l.Count <> 0 do
let v = l.[l.Count - 1]
if cache.ContainsKey(v) then l.RemoveAt(l.Count - 1)
else
try
cache.[v] <- f (fun x ->
if cache.ContainsKey(x) then cache.[x]
else
l.Add(x)
failwith "Need to recurse") v
with _ -> ()
cache.[x]
不幸的是，插入到每个递归调用中的机器有点重，因此需要深度递归的非记忆输入的性能可能会有点慢。但是，与其他一些解决方案相比，这样做的好处是它需要对递归函数的自然表达式进行相当小的更改：
let fib = memoY (fun fib n ->
printfn "%i" n;
if n <= 1 then n
else (fib (n-1)) + (fib (n-2)))
let _ = fib 5000
编辑
我将稍微扩展一下这与其他解决方案的比较。这种技术利用了异常提供了一个辅助通道这一事实：类型的函数'a -> 'b实际上不需要返回类型的值'b，而是可以通过异常退出。如果返回类型明确包含指示失败的附加值，我们就不需要使用异常。当然，我们可以'b option为此目的使用函数的返回类型。这将导致以下记忆组合器：
let memoO f =
let cache = Dictionary<_,_>()
fun x ->
let l = ResizeArray([x])
while l.Count <> 0 do
let v = l.[l.Count - 1]
if cache.ContainsKey v then l.RemoveAt(l.Count - 1)
else
match f(fun x -> if cache.ContainsKey x then Some(cache.[x]) else l.Add(x); None) v with
| Some(r) -> cache.[v] <- r;
| None -> ()
cache.[x]
以前，我们的记忆过程看起来像：
fun fib n ->
printfn "%i" n;
if n <= 1 then n
else (fib (n-1)) + (fib (n-2))
|> memoY
fib现在，我们需要合并应该返回一个int option而不是一个的事实int。给定一个适合option类型的工作流，可以这样写：
fun fib n -> option {
printfn "%i" n
if n <= 1 then return n
else
let! x = fib (n-1)
let! y = fib (n-2)
return x + y
} |> memoO
但是，如果我们愿意更改第一个参数的返回类型（在本例中为 fromint到int option），我们不妨一路走下去，只在返回类型中使用延续，就像在 Brian 的解决方案中一样。这是他定义的一个变体：
let memoC f =
let cache = Dictionary<_,_>()
let rec fn n k =
match cache.TryGetValue(n) with
| true, r -> k r
| _ ->
f fn n (fun r ->
cache.Add(n,r)
k r)
fun n -> fn n id
同样，如果我们有一个合适的计算表达式来构建 CPS 函数，我们可以像这样定义我们的递归函数：
fun fib n -> cps {
printfn "%i" n
if n <= 1 then return n
else
let! x = fib (n-1)
let! y = fib (n-2)
return x + y
} |> memoC
这与 Brian 所做的完全相同，但我发现这里的语法更容易理解。为了完成这项工作，我们只需要以下两个定义：
type CpsBuilder() =
member this.Return x k = k x
member this.Bind(m,f) k = m (fun a -> f a k)
let cps = CpsBuilder()