6

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).

FooBee
  • 778
  • 7
  • 23
Jan Stolarek
  • 1,409
  • 1
  • 11
  • 21
  • What happens when you do not trace the function call? What happens when you use another scheme system? – knivil Mar 16 '12 at 08:29
  • Disabling trace doesn't help. Racket does fine with the given example. – Jan Stolarek Mar 16 '12 at 08:32
  • 7
    This might be a bug: that definition looks tail-recursive. (Most tracing libraries will destroy the tail-recursiveness, though.) – Eli Barzilay Mar 16 '12 at 10:19
  • I tried this on ubuntu and it seems to be working fine. Which OS you are using? – Ankur Mar 16 '12 at 12:12
  • This is on openSUSE 11.3, but I think this may be fault of older version of Guile (2.x versions are available, but not for my system). Anyway, if this definition is correct that everything is OK, I was afraid I misunderstood something about tail recursion. – Jan Stolarek Mar 17 '12 at 09:49
  • FWIW, I just tried this in guile-2.0.1 and guile-1.8.5, without tracing, and got no stack overflow – gcbenison Mar 19 '12 at 19:33
  • Works fine guile 1.8.7 on Debian amd64. http://pastebin.com/8EYDwpY1 – Zang MingJie Mar 24 '12 at 18:00
  • For what it's worth, it worked with TinyScheme 1.39, on Solaris SPARC 32-bit. – rahmu Apr 10 '12 at 16:42
  • am I the only one botherd by it only ever returning `1`? – wowest Apr 12 '12 at 15:41

2 Answers2

2

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).

Óscar López
  • 232,561
  • 37
  • 312
  • 386
0
(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?

wowest
  • 1,974
  • 14
  • 21