6

我在 Scheme 中写过 Collat​​z 猜想：

(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）。

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 回答