6

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

適切な末尾再帰がオーバーフローを引き起こすのはなぜですか? ご覧のとおり、Scheme インタープリターとして Guile を使用しています (バージョン 1.8.7)。

4

2 に答える 2

2

定義された手順は、Racket で正常に機能します。私にはバグのように思えますが、あなたの環境に非常に特有のもののようです。

ほぼ確実にあなたの問題とは関係ありませんが、少し補足します: の(= n 1)代わりに数値の比較を使用して(eq? n 1)ください。

于 2012-04-10T21:19:03.993 に答える
0 
(define C
  (lambda (n)
    (cond
     ((eq? n 1) 1)
     ((even? n) (C (/ n 2)))
     (else (C (+ (* n 3) 1))))))

これは常に戻るように見えます1（または無限にループします-推測は証明されていません）。(+1 ...)再帰呼び出しの周りに隠れている転記エラーはありますか?

于 2012-04-10T19:59:20.017 に答える