Why is tail recursive Collatz conjecture causing stack overflow in Scheme?
-
24-05-2021 - |
Question
I've written Collatz conjecture in Scheme:
(define C
(lambda (n)
(cond
((eq? n 1) 1)
((even? n) (C (/ n 2)))
(else (C (+ (* n 3) 1))))))
This is a tail recursive call, yet I get stack overflow when I call (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)
Why is proper tail recursion causing an overflow? As you can see, I'm using Guile as a Scheme interpreter (version 1.8.7).
Solution
The procedure as defined works fine in Racket. It seems like a bug to me, or something very specific to your environment.
Almost certainly not related to your problem, but a bit of nit-picking: use the comparison (= n 1)
for numbers instead of (eq? n 1)
.
OTHER TIPS
(define C
(lambda (n)
(cond
((eq? n 1) 1)
((even? n) (C (/ n 2)))
(else (C (+ (* n 3) 1))))))
This looks like it always returns 1
(or loops infinitely -- the conjecture remains unproven). Is there a transcription error hiding a (+1 ...)
around the recursive calls?
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow