StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POHow do I memoize a recursive function in Lisp?
text
Body
copied!<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&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 ((> steps maxsteps) (setq maxsteps steps) (setq n i)) (t ()))) n)) (defun memoize (fn) (let ((cache (make-hash-table :test #'equal))) #'(lambda (&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>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload