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) 需要相當長的時間來計算，甚至如果用盡記憶體，還可能會讓你的解析器崩潰。