advice.el

(defadvice rec-fib (around rec-fib-memoize compile activate)
  (let* ((memo-table (memo-table-for-symbol 'rec-fib))
         (arg (ad-get-arg 0))
         (result (gethash arg memo-table)))
    (if result
        (setq ad-return-value result)
      ad-do-it
      (puthash arg ad-return-value memo-table))))

fib.el

(defun rec-fib (arg)
  (if (<= arg 2)
      1
    (+ (rec-fib (- arg 1))
       (rec-fib (- arg 2)))))

memoise.el

(defmacro memoise (fn)
  (let ((advice-name (memo-advice-name fn)))
    `(defadvice ,fn (around ,advice-name compile activate)
       (let* ((memo-table (memo-table-for-symbol ',fn))
              (arg (ad-get-arg 0))
              (result (gethash arg memo-table)))
         (if result
             (setq ad-return-value result)
           ad-do-it
           (puthash arg ad-return-value memo-table))))))

undo.el

(defun remove-memoisation (fn)
  (let ((advice-name (memo-advice-name fn)))
    (ad-remove-advice fn 'around advice-name)
    (ad-update fn)
    (put fn 'memo-table nil)))

(defun reset-memoisation-cache (fn)
  (put fn 'memo-table (make-hash-table :test 'equal)))

usage.el

(rec-fib 34) ;; Takes 5-6s for me
(memoise rec-fib)
(rec-fib 34) ;; Instantaneous
(remove-memoisation 'rec-fib)
(rec-fib 34) ;; Slow again

utilities.el

(defun memo-table-for-symbol (sym)
  (let ((memo-table (get sym 'memo-table)))
    (if memo-table
        memo-table
      (put sym 'memo-table (make-hash-table :test 'equal)))))

(defun memo-advice-name (sym)
  (intern (concat (symbol-name sym) "-memoise")))