All geek questions in one place

Why does the Collatz tail recursive hypothesis cause a stack overflow in a Schema?

I wrote the Collatz hypothesis in the diagram:

(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, but I get a stack overflow on 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 does proper tail recursion cause overflow? As you can see, I use Guile as a schema interpreter (version 1.8.7).

+6
source share
2 answers

The procedure, as defined, works great in Racket. This seems like a mistake to me or something very specific to your environment.

Almost certainly not related to your problem, but a bit nit-picking: use comparison (= n 1) for numbers instead of (eq? n 1) .

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

It seems that it always returns 1 (or the loop is infinite - the hypothesis remains unproven). Is there a transcription error hiding a (+1 ...) around recursive calls?

0
source

Source: https://habr.com/ru/post/910882/

More articles:


All Articles