爲什麼尾部遞歸Collatz猜想會導致Scheme中堆棧溢出？

我已經寫在Collatz猜想方案：爲什麼尾部遞歸Collatz猜想會導致Scheme中堆棧溢出？

(define C 
    (lambda (n) 
    (cond 
    ((eq? n 1) 1) 
    ((even? n) (C (/ n 2))) 
    (else (C (+ (* n 3) 1))))))

這是一個尾遞歸調用，但我得到堆棧溢出，當我打電話（C 121）：

guile> (trace C) 
(C) 
guile> (C 121) 
[C 121] 
[C 364] 
[C 182] 
[C 91] 
[C 274] 
[C 137] 
[C 412] 
[C 206] 
[C 103] 
[C 310] 
[C 155] 
[C 466] 
[C 233] 
[C 700] 
[C 350] 
[C 175] 
[C 526] 
[C 263] 
[C 790] 
[C 395] 
[C 1186] 
ERROR: Stack overflow 
ABORT: (stack-overflow)

爲什麼是正確的尾遞歸造成溢出？正如你所看到的，我使用Guile作爲Scheme解釋器（版本1.8.7）。

來源

2012-03-16 Jan Stolarek

當你不跟蹤函數調用時會發生什麼？當你使用另一個計劃系統會發生什麼？ – knivil 2012-03-16 08:29:55

禁用跟蹤不起作用。球拍與給定的例子很好。 – 2012-03-16 08:32:36

這可能是一個錯誤：該定義看起來是尾遞歸的。（儘管大多數追蹤庫會破壞尾部遞歸。） – 2012-03-16 10:19:58

程序所定義的球拍工作正常。這對我來說似乎是一個錯誤，或者對你的環境非常特殊。

幾乎肯定與您的問題無關，但有點挑剔：使用比較(= n 1)而不是(eq? n 1)。

來源

2012-04-10 21:19:03

(define C 
    (lambda (n) 
    (cond 
    ((eq? n 1) 1) 
    ((even? n) (C (/ n 2))) 
    (else (C (+ (* n 3) 1))))))

這看起來像它總是返回1（或循環無限 - 猜想仍未證實）。圍繞遞歸調用隱藏(+1 ...)是否存在轉錄錯誤？

來源

2012-04-10 19:59:20 wowest

爲什麼尾部遞歸Collat​​z猜想會導致Scheme中堆棧溢出？

回答

相關問題

爲什麼尾部遞歸Collatz猜想會導致Scheme中堆棧溢出？