关于F#通用Memoization函数及斐波那契实现的疑问

一、原始斐波那契实现为何能保留映射？ #

先看你的memoize函数：

let memoize f =
    let dict = new Dictionary<_,_>()
    fun n ->
        match dict.TryGetValue(n) with
        | (true, v) -> 
            v
        | _ ->
            let temp = f(n)
            dict.Add(n, temp)
            temp

这个函数的核心是闭包特性：当你调用memoize f时，会创建一个新的Dictionary，然后返回一个匿名函数。这个匿名函数会捕获外层的dict变量，形成闭包——也就是说，这个匿名函数会永久持有对该dict的引用。

再看你的原始斐波那契定义：

let rec fib = memoize(fun n ->
    if n = 1 then 1
    elif n = 2 then 1
    else fib (n - 1) + fib (n - 2) )

这里fib是一个绑定到闭包的变量，而非普通函数。当你第一次定义fib时，memoize只被调用一次：它创建了唯一的Dictionary，返回捕获该字典的匿名函数，并把这个函数赋值给fib。

后续所有对fib的调用（包括递归里的fib(n-1)、fib(n-2)），都是在调用同一个闭包函数，自然共享同一个dict，所以所有计算过的节点都会被缓存下来，不会每次迭代都创建新字典。

你之前的误解是以为每次递归调用都会触发memoize，但实际上memoize只在定义fib时执行了一次，后续递归调用的是memoize返回的闭包，不会重新创建字典。

二、修改后的版本为何失去记忆化效果？ #

修改后的代码：

let rec fib i = memoize(fun n ->
    if n = 1 then 1
    elif n = 2 then 1
    else fib (n - 1) + fib (n - 2) ) i

这里fib变成了一个普通递归函数，每次调用fib i时，函数体都会完整执行一遍：也就是每次调用都会重新调用memoize(...)，而每次调用memoize都会创建一个全新的Dictionary，生成新的闭包后再调用i。

更关键的是，递归调用fib(n-1)和fib(n-2)时，同样会各自触发memoize的调用，每次都生成新字典。这就导致所有缓存都是临时的，每次调用fib都会从头开始计算，完全失去了记忆化的作用。

消除警告同时保留记忆化的正确写法 #

要解决这个问题，需要让memoize只执行一次，同时避免递归对象的警告。推荐用以下两种方式：

方法一：分离递归逻辑与记忆化

let fib = 
    let rec helper n =
        if n = 1 then 1
        elif n = 2 then 1
        else helper (n-1) + helper (n-2)
    memoize helper

这里helper是普通递归函数，memoize helper只执行一次，返回的闭包赋值给fib，既没有警告，又完整保留了记忆化效果。

方法二：延迟初始化递归闭包

如果你想保留原有的递归闭包写法，可以用lazy延迟初始化：

let rec fib = lazy (memoize(fun n ->
    if n = 1 then 1
    elif n = 2 then 1
    else fib.Value (n - 1) + fib.Value (n - 2) ))

// 调用时需使用 fib.Value n

不过这种写法不如第一种简洁，优先推荐方法一。

内容的提问来源于stack exchange，提问作者pengqr