title: How do I memoize a recursive function in Lisp?
body: <p>I'm a Lisp beginner. I'm trying to memoize a recursive function for calculating the number of terms in a <a href="http://en.wikipedia.org/wiki/Collatz_conjecture" rel="noreferrer">Collatz sequence</a> (for problem 14 in <a href="http://projecteuler.net/index.php?section=problems&amp;id=14" rel="noreferrer">Project Euler</a>). My code as of yet is:</p>
  
  <pre><code>(defun collatz-steps (n)
    (if (= 1 n) 0
         (if (evenp n) 
             (1+ (collatz-steps (/ n 2)))
             (1+ (collatz-steps (1+ (* 3 n)))))))
  
  (defun p14 ()
    (defvar m-collatz-steps (memoize #'collatz-steps))
    (let 
        ((maxsteps (funcall m-collatz-steps 2))
         (n 2)
         (steps))
      (loop for i from 1 to 1000000
            do 
            (setq steps (funcall m-collatz-steps i))
            (cond 
              ((&gt; steps maxsteps) 
               (setq maxsteps steps)
               (setq n i))
              (t ())))
      n))
  
  
  (defun memoize (fn)
    (let ((cache (make-hash-table :test #'equal)))
      #'(lambda (&amp;rest args)
          (multiple-value-bind 
                (result exists)
              (gethash args cache)
            (if exists
                result
                (setf (gethash args cache)
                      (apply fn args)))))))
  </code></pre>
  
  <p>The memoize function is the same as the one given in the <a href="http://lib.store.yahoo.net/lib/paulgraham/onlisp.pdf" rel="noreferrer">On Lisp</a> book. </p>
  
  <p>This code doesn't actually give any speedup compared to the non-memoized version. I believe it's due to the recursive calls calling the non-memoized version of the function, which sort of defeats the purpose. In that case, what is the correct way to do the memoization here? Is there any way to have all calls to the original function call the memoized version itself, removing the need for the special m-collatz-steps symbol?</p>
  
  <p>EDIT: Corrected the code to have </p>
  
  <pre><code>(defvar m-collatz-steps (memoize #'collatz-steps))
  </code></pre>
  
  <p>which is what I had in my code. 
  Before the edit I had erroneously put:</p>
  
  <pre><code>(defvar collatz-steps (memoize #'collatz-steps))
  </code></pre>
  
  <p>Seeing that error gave me another idea, and I tried using this last defvar itself and changing the recursive calls to </p>
  
  <pre><code>       (1+ (funcall collatz-steps (/ n 2)))
         (1+ (funcall collatz-steps (1+ (* 3 n))))
  </code></pre>
  
  <p>This does seem to perform the memoization (speedup from about 60 seconds to 1.5 seconds), but requires changing the original function. Is there a cleaner solution which doesn't involve changing the original function? </p>