0

一直在课堂上玩 LISP。这无疑是我编写的第一个 LISP 代码。我无法弄清楚为什么此代码会为"invocation stack history overflow"函数的输入值超过 2000产生错误(longest_collatz n)。有更多这门语言经验的人可以帮助我理解错误吗？

(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)))
4

2 回答 2

2

Youtcollatz函数不是尾递归的，因此即使编译代码也不太可能将其转换为循环。

您可以使用累加器重写它，以便编译器将其转换为循环：

(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)))))

（这是一个 bug-for-bug 的重新实现）。

笔记：

  1. 避免elt；使用firstandsecond会更好。
  2. 重写maxlistusingreduce会使它更快更清晰。
于 2014-04-11T16:28:48.577 回答
0

这是一个只返回 collat​​z 列表的长度而不是列表本身的函数。它可能更有效（并且是尾递归的）。

(defun collatz_length2 (n cnt)
  (if (<= n 1)
    cnt
    (if (= (mod n 2) 0)
      (collatz_length2 (/ n 2) (1+ cnt))
      (collatz_length2 (+ (* n 3) 1) (1+ cnt)))))

(defun collatz_length (n) (collatz_length2 n 1))
于 2014-04-11T19:28:15.327 回答