在课堂上一直在玩LISP。无可否认,这是我编写的第一个LISP代码。我不明白为什么对于函数(longest_collatz n)
的输入值超过2000,此代码会产生错误"invocation stack history overflow"
。有谁能在这门语言方面有更多的经验来帮助我理解这个错误吗?
(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)))
Yout collatz
函数不是尾递归函数,因此即使编译代码,它也不太可能转换为循环。
您可以使用累加器对其进行重写,以便编译器将其转换为循环:
(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的bug)。
注:
- 避免
elt
;使用CCD_ 5和CCD_ - 使用
reduce
重写maxlist
将使其更快、更清晰
这里有一个函数,它只返回collatz列表的长度,而不是列表本身。它可能更高效(并且是尾部递归的)。
(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))