Invocation Stack History Overflow

Question

Been playing around with LISP in class. This is admittedly the first LISP code I've written. I can't figure out why this code produces the error "invocation stack history overflow" for input values over 2000 to the function (longest_collatz n). Can anyone with more experience in this language help me understand the error?

(defun longest_collatz(n)
  (reverse 
   (maxlist
    (loop for x from 1 to n
       collect (list x (length (collatz x)))))))

(defun collatz (n)
  (if (<= n 1)
      '(1)
      (if (= (mod n 2) 0)
          (cons (/ n 2) (collatz (/ n 2)))
          (cons (+ (* n 3) 1) (collatz (+ (* n 3) 1))))))

(defun maxlist (z)
  (if (> (length z) 1)
      (if (< (cadr (elt z 0)) (cadr (elt z 1)))
          (maxlist (cdr z))
          (maxlist (cons (elt z 0) (cddr z))))
      (car z)))

Answer 1

Yout collatz function is not tail recursive, so it is unlikely that it is converted to a loop even if you compile your code.

You can rewrite it using an accumulator, so that it is converted to a loop by the compiler:

(defun collatz (n &optional acc)
  (unless (plusp n)
    (error "~s(~s): positive argument is required" 'collatz n))
  (if (= n 1)
      (nreverse (cons 1 acc))
      (let ((next (if (evenp n)
                      (ash n -1) ; same as (mod n 2)
                      (1+ (* n 3)))))
        (collatz next (cons next acc)))))

(this is a bug-for-bug reimplementation).

Notes:

1. Avoid elt; using first and second instead would be must better.
2. Rewriting maxlist using reduce would make it both faster and clearer.