호출 스택 오버플로 오버플로

Question

클래스에서 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))) 

Answer 1

이 행해져 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))))) 

(이 버그를 위해 버그를 다시 구현입니다).

주 :

1. 피 elt; 대신 first 및 second을 사용하는 것이 좋습니다.
2. maxlist을 reduce으로 다시 쓰면 더 빠르고 명확 해집니다.

Answer 2

다음은 목록 자체 대신에 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))