在Scheme中使用关联列表实现阶乘函数记忆化遇到问题

我来帮你排查下这个记忆化失效的问题～ 用关联列表做阶乘记忆化的思路本身没问题，但你大概率踩了Scheme不可变数据+全局变量更新的坑，下面一步步拆解问题并给出解决办法：

问题根源 #

你初始化了全局关联列表al，但如果你的绑定函数只是生成新的关联列表、却没有用set!更新al的全局绑定，那么每次查找时al始终是空列表，自然起不到缓存效果。另外，全局变量本身也容易引发意外的副作用，不是最优选择。

方案1：修复全局关联列表的实现 #

先把你的代码补全并修正核心问题——必须用set!更新全局的关联列表：

; 初始化全局关联列表
(define al '())

; 从关联列表中查找n对应的缓存值
(define (lookup n)
  (assoc n al))

; 将n和计算结果绑定到关联列表，并更新全局al
(define (bind n val)
  (set! al (cons (cons n val) al)))

; 记忆化阶乘函数
(define (memo-fac n)
  (cond ((<= n 1) 1)
        (else
         ; 先查缓存
         (let ((cached-result (lookup n)))
           (if cached-result
               ; 命中缓存，直接返回值
               (cdr cached-result)
               ; 未命中，计算后缓存结果
               (let ((new-result (* n (memo-fac (- n 1)))))
                 (bind n new-result)
                 new-result))))))

测试一下：

• 第一次调用(memo-fac 5)会计算所有中间值，之后查看al会得到((5 . 120) (4 . 24) (3 . 6) (2 . 2))
• 再次调用(memo-fac 5)会直接返回缓存的120，不会重复计算

方案2：更优雅的闭包封装（推荐） #

全局变量容易引发副作用，用闭包把关联列表封装在函数内部，只有记忆化函数能访问它，更安全也更符合函数式风格：

(define memo-fac
  ; 闭包内部维护缓存列表，外部无法直接修改
  (let ((cache '()))
    ; 内部查找函数
    (define (lookup n)
      (assoc n cache))
    ; 内部绑定函数
    (define (bind n val)
      (set! cache (cons (cons n val) cache)))
    ; 返回记忆化的阶乘函数
    (lambda (n)
      (cond ((<= n 1) 1)
            (else
             (let ((cached (lookup n)))
               (if cached
                   (cdr cached)
                   (let ((result (* n (memo-fac (- n 1)))))
                     (bind n result)
                     result)))))))

这种方式下，缓存列表cache是完全私有的，不会和全局环境中的其他变量冲突，代码更健壮。

你可能踩的坑 #

如果你的bind函数只是返回新的关联列表（比如(define (bind n val) (cons (cons n val) al))），却没有用set!更新al的绑定，那么al永远是空列表，查找永远不会命中，这就是记忆化失效的核心原因。

内容的提问来源于stack exchange，提问作者Gabe S.