Почему хвостовая рекурсивная гипотеза Коллатца вызывает переполнение стека в Схеме? - PullRequest
Новая
       41

Почему хвостовая рекурсивная гипотеза Коллатца вызывает переполнение стека в Схеме?

6 голосов
/ 16 марта 2012

Я написал гипотезу Коллатца на схеме: 

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

Ответы [ 2 ]

2 голосов
/ 11 апреля 2012

Процедура, как определено, прекрасно работает в Racket. Мне кажется, это ошибка или что-то очень специфичное для вашей среды.

Почти наверняка не связано с вашей проблемой, но немного придирчиво: используйте сравнение (= n 1) для чисел вместо (eq? n 1).

0 голосов
/ 10 апреля 2012 
(define C
  (lambda (n)
    (cond
     ((eq? n 1) 1)
     ((even? n) (C (/ n 2)))
     (else (C (+ (* n 3) 1))))))

Похоже, он всегда возвращает 1 (или повторяется бесконечно - гипотеза остается недоказанной)Есть ли ошибка транскрипции, скрывающая (+1 ...) вокруг рекурсивных вызовов?

...