Common Lisp : 꼬리 재귀 함수가 스택 오버플로를 일으키는 이유는 무엇입니까?

Question

Common Lisp 함수의 성능을 이해하는 데 문제가 있습니다 (아직 초보자입니다). 필자는이 함수의 두 가지 버전을 가지고 있습니다.이 함수는 단순히 주어진 n까지 모든 정수의 합을 계산합니다.

비 꼬리 재귀 버전 :

(defun addup3 (n) 
    (if (= n 0) 
    0 
    (+ n (addup (- n 1))))) 

꼬리 재귀 버전 : I 입력 n = 1000000와 CLISP에서이 기능을 실행하려고

(defun addup2 (n) 
    (labels ((f (acc k) 
       (if (= k 0) 
        acc 
        (f (+ acc k) (- k 1))))) 
    (f 0 n))) 

. 여기에 결과

[2]> (addup3 1000000) 
500000500000 
[3]> (addup2 1000000) 

*** - Program stack overflow. RESET 

내가 SBCL 모두 성공적으로 실행할 수 있지만 비 꼬리 재귀 하나는 빠른 (만 조금씩, 그러나 그것은 나에게 이상한 것 같다). 내가 Stackoverflow 질문에 대한 답변을 찾았지만 비슷한 것을 찾을 수 없습니다. 꼬리 재귀 함수가 모든 재귀 함수 호출을 스택에 넣지 않도록 설계되었지만 스택 오버플로가 발생하는 이유는 무엇입니까? 꼬리 호출을 최적화하도록 인터프리터/컴파일러에 알려야합니까? (나는 디버그 레벨을 설정하고 추적 기능의 비용으로 최적화하기 위해 (proclaim '(optimize (debug 1))과 같은 것을 읽었지만 이것이 무엇을하는지는 알지 못한다.) 어쩌면 그 해답은 분명하고 코드는 엉터리 일지 모르지만, 나는 그걸 알아 내지 못합니다. 도움을 주시면 감사하겠습니다.

편집 : danlei가 오타를 지적 했으므로 첫 번째 함수에서 addup3을 호출해야하므로 재귀 적입니다. 수정 된 경우는 그것을 할 수있는 전형적인 방법이 될 수 있지만, 두 버전 오버 플로우,하지만 하나

(defun addup (n) 
     "Adds up the first N integers" 
     (do ((i 0 (+ i 1)) 
       (sum 0 (+ sum i))) 
      ((> i n) sum))) 

, 나는 그것이 이상한 그건 말해 같은 꼬리 재귀가 항상 내 강사를 고려, 최적화되지 않은 것을 발견 그의 없습니다 훨씬 더 효율적이고 물건.

Answer 1

커먼 리스프 구현에서 꼬리 호출 최적화가 필요하지 않습니다. 대부분 (그러나 나는 자바 가상 머신의 한계 때문에 ABCL이 그렇지 않다고 생각한다.)

TCO가있는 경우 어떤 최적화 설정을 선택해야하는지 알려주는 문서 (사용 가능한 경우). 물론, "작은 가우스"를 사용하는 것이 좋습니다이 경우

(loop :for i :upto n 
     :sum i) 

(let ((sum 0)) 
    (dotimes (i n) 
    (incf sum (1+ i)))) 

(do ((i 0 (1+ i)) 
    (sum 0 (+ sum i))) 
    ((> i n) sum)) 

:

IT는 반복 구조 중 하나를 사용하는 커먼 리스프 코드에 대한 더 관용적이다

(/ (* n (1+ n)) 2) 

Answer 2

글쎄, addup3은 단지 에에 재귀 적이 아닙니다.

(defun addup3 (n) 
    (if (= n 0) 
    0 
    (+ n (addup (- n 1))))) ; <-- 

무엇이든간에 addup을 호출합니다. SBCL의 수정 된 버전을 시도 :

CL-USER> (defun addup3 (n) 
      (if (= n 0) 
       0 
       (+ n (addup3 (- n 1))))) 
ADDUP3 
CL-USER> (addup3 100000) 
Control stack guard page temporarily disabled: proceed with caution 
; .. 
; Evaluation aborted on #<SB-SYS:MEMORY-FAULT-ERROR {C2F19B1}>. 

를 예상대로.

Answer 3

GNU CommonLisp을 사용하여 GCL 2.6.12, addup2의 컴파일이 꼬리 호출을 최적화합니다, 여기에 내가 가진 무엇 :

>(compile 'addup2)                  

Compiling /tmp/gazonk_3012_0.lsp. 
End of Pass 1. 

;; Note: Tail-recursive call of F was replaced by iteration. 
End of Pass 2. 
OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3 
Finished compiling /tmp/gazonk_3012_0.lsp. 
Loading /tmp/gazonk_3012_0.o 
start address -T 0x9556e8 Finished loading /tmp/gazonk_3012_0.o 
#<compiled-function ADDUP2> 
NIL 
NIL 

>>(addup2 1000000)                                    

500000500000 
>(addup3 1000000) 

Error: ERROR "Invocation history stack overflow." 
Fast links are on: do (si::use-fast-links nil) for debugging 
Signalled by IF. 
ERROR "Invocation history stack overflow." 

Broken at +. Type :H for Help. 
    1 Return to top level. 

>>(compile 'addup3)                                   

Compiling /tmp/gazonk_3012_0.lsp. 
End of Pass 1. 
End of Pass 2. 
OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3 
Finished compiling /tmp/gazonk_3012_0.lsp. 
Loading /tmp/gazonk_3012_0.o 
start address -T 0x955a00 Finished loading /tmp/gazonk_3012_0.o 
#<compiled-function ADDUP3> 
NIL 
NIL 
>>(addup3 1000000)                                    

Error: ERROR "Value stack overflow." 

는 도움이되기를 바랍니다.