Scheme中传入已定义过程与lambda表达式作为参数结果不同的问题

我来帮你拆解这个问题——这其实是Scheme里过程引用和递归绑定的经典陷阱，很多人刚接触SICP的记忆化章节时都会踩这个坑！

问题根源：递归调用的指向不对 #

先看你的代码：
你定义的原始fib过程，内部递归调用的是全局绑定的fib，也就是未记忆化的版本。当你直接把fib传给memoize时：

(define memo-fib (memoize fib))

此时memoize里的f绑定的是原始fib。当你调用(memo-fib 3)时，最外层会查记忆表，发现没有就调用(f 3)，也就是原始fib。而原始fib内部的(fib (-n 1))和(fib (-n 2))会直接调用全局的原始fib，完全不会经过记忆表！这就是为什么你看到还是重复打印"computing fib of..."的原因。

但如果你用lambda作为参数，比如这样写：

(define memo-fib
  (memoize
   (lambda (n)
     (display "computing fib of ")
     (display n)
     (newline)
     (cond ((= n 0) 0)
           ((= n 1) 1)
           (else (+ (memo-fib (- n 1)) (memo-fib (- n 2))))))))

这时lambda内部的递归调用指向的是已经绑定的memo-fib（也就是记忆化后的过程），所以每次递归都会先查记忆表，自然就不会重复计算了。

正确的实现方式 #

这里有两种常见的解决思路：

1. 让递归直接引用记忆化过程（SICP原版写法）

直接在lambda内部引用memo-fib，这样所有递归调用都会走记忆化逻辑：

(define (memoize f)
  (let ((table (make-table)))
    (lambda (x)
      (let ((previously-computed-result (lookup x table)))
        (or previously-computed-result
            (let ((result (f x)))
              (insert! x result table)
              result))))))

(define memo-fib
  (memoize
   (lambda (n)
     (display "computing fib of ")
     (display n)
     (newline)
     (cond ((= n 0) 0)
           ((= n 1) 1)
           (else (+ (memo-fib (- n 1)) (memo-fib (- n 2))))))))

2. 用letrec创建自引用的递归过程

如果你不想依赖外部的memo-fib绑定，可以用letrec创建一个自引用的内部过程，再传给memoize：

(define (memoize f)
  (let ((table (make-table)))
    (lambda (x)
      (let ((previously-computed-result (lookup x table)))
        (or previously-computed-result
            (let ((result (f x)))
              (insert! x result table)
              result))))))

(define memo-fib
  (letrec ((fib-inner
            (lambda (n)
              (display "computing fib of ")
              (display n)
              (newline)
              (cond ((= n 0) 0)
                    ((= n 1) 1)
                    (else (+ (fib-inner (- n 1)) (fib-inner (- n 2))))))))
    (memoize fib-inner)))

这里fib-inner内部递归调用自己，而fib-inner被memoize包裹后，所有调用都会先查记忆表，效果和第一种方法一样。

总结一下 #

核心区别在于：

• 直接传原始fib给memoize时，内部递归还是调用未记忆化的原始过程，记忆表只作用于最外层调用。
• 用lambda或letrec让递归调用指向记忆化后的过程，才能让所有递归步骤都走记忆表，真正实现记忆化优化。

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