Scheme 编程/备忘

备忘是一种编程技巧，允许程序记住先前计算的结果。此技巧有很多好处；在这里，我们将讨论它在加速某些算法中的用法。

例如，以下程序用于计算斐波那契数列，是正确的，但速度很慢

(define fibonacci 
  (lambda (n)
    (cond
      ((or (= n 1) (= n 2)) 1)
      (else (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))))

对于那些对算法分析有了解的人来说，他们会注意到，对于 n > 2 的每个 (fibonacci n) 调用都需要再调用两次 fibonacci 函数，因此，该算法的最坏情况运行时间为 O(2ⁿ)。我们显然可以做得更好。观察 (fibonacci 1000) 需要相当长的时间来计算，甚至如果用尽内存，还可能会让你的解析器崩溃。