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

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

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


stack-overflow lisp scheme guile collatz
person Jan Stolarek    schedule 16.03.2012    source источник
comment
Что происходит, когда вы не отслеживаете вызов функции? Что происходит, когда вы используете другую систему схемы?   -  person knivil    schedule 16.03.2012
comment
Отключение трассировки не помогает. Racket отлично справляется с данным примером.   -  person Jan Stolarek    schedule 16.03.2012
comment
Это может быть ошибкой: это определение выглядит как хвостовая рекурсия. (Однако большинство библиотек трассировки уничтожат хвостовую рекурсию.)   -  person Eli Barzilay    schedule 16.03.2012
comment
Я попробовал это на ubuntu, и, кажется, он работает нормально. Какую ОС вы используете?   -  person Ankur    schedule 16.03.2012
comment
Это на openSUSE 11.3, но я думаю, что это может быть ошибка старой версии Guile (доступны версии 2.x, но не для моей системы). В любом случае, если это определение правильное, то все в порядке, я боялся, что неправильно понял что-то о хвостовой рекурсии.   -  person Jan Stolarek    schedule 17.03.2012
comment
FWIW, я только что попробовал это в guile-2.0.1 и guile-1.8.5, без трассировки, и не получил переполнения стека.   -  person gcbenison    schedule 19.03.2012
comment
Отлично работает guile 1.8.7 на Debian amd64. pastebin.com/8EYDwpY1   -  person Zang MingJie    schedule 24.03.2012
comment
Как бы то ни было, он работал с TinyScheme 1.39 на 32-разрядной версии Solaris SPARC.   -  person rahmu    schedule 10.04.2012
comment
меня единственного беспокоит, что это только когда-либо возвращает 1?   -  person wowest    schedule 12.04.2012

Ответы (2)


arrow_upward
2
arrow_downward

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

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

person Óscar López    schedule 10.04.2012

arrow_upward
0
arrow_downward 

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

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

person wowest    schedule 10.04.2012