Optimize Lisp recursive random walk

Question

This function results in stack overflow for more than about 2000 steps, is there any way I can easily optimize it to use less memory?

(defun randomwalk (steps state)
(displaystate state)
(if (equal steps 0) nil
        (if (solved? state) t
            (let ((nrmlstate (normalize state)))
                (randomwalk (- steps 1) (applymove nrmlstate (nth (random 
(length (getallmoves nrmlstate))) (getallmoves nrmlstate))))
            )
        )
    )
)

Answer 1

It looks like you only call in tail position which means you can easily rewrite it to not recurse at all:

(defun randomwalk (steps state)
  (loop :if (= steps 0)     
            :do (return nil)
        :if (solved? state) 
            :do (return t)
        :else
            :do (let* ((nrmlstate (normalize state))
                       (moves (getallmoves nrmlstate))
                       (random-move (nth (random (length moves)) moves)))
                  (setf state (applymove nrmlstate random-move))
                  (decf steps))))

Since I don't have the functions you use I have not been able to test it other than for the base cases.