調用堆棧歷史溢出

在課堂上玩過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)))

來源

2014-04-11 Dagrooms

它似乎並不適合我。 '（longest_collatz 3000）'返回'（217 2919）'在'SBCL 1.1.11'上。你使用的是什麼實現和版本？一般來說，Common Lisp不保證tail-call消除，所以我認爲你的'maxlist'會成爲大輸入的問題。 – Inaimathi

你能告訴我們你的功能應該做什麼嗎？描述每一個。顯示輸入和輸出。 – ooga

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

（這是一個錯誤換錯誤重新實現）。

注：

避免elt;使用first和second反而會更好。
重寫maxlist使用reduce會使它更快更清晰。

來源

2014-04-11 16:28:48 sds

這只是問題的一部分。你可以讓整個事情尾遞歸？並沒有任何理由返回實際列表;只是長度就足夠了。 – ooga

@ooga：我做了'collatz' TR; 'maxlist'已經是TR，但爲了速度和清晰度（並避免考慮）應該重寫爲使用'reduce'。 – sds

我在考慮'longest_collatz'函數。您的整個解決方案是否適用於數十億的數字？ '（longest_collatz 1000000000'）的答案是什麼？ – ooga

這是一個函數，它只返回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))

來源

2014-04-11 19:28:15 ooga

調用堆棧歷史溢出

回答

相關問題