У меня проблема с пониманием производительности функции Common Lisp (я все еще новичок). У меня есть две версии этой функции, которая просто вычисляет сумму всех целых чисел до заданного n.Common Lisp: Почему моя хвостовая рекурсивная функция вызывает переполнение стека?
Non-хвост рекурсивной версии:
(defun addup3 (n)
(if (= n 0)
0
(+ n (addup (- n 1)))))
Tail-рекурсивная версия:
(defun addup2 (n)
(labels ((f (acc k)
(if (= k 0)
acc
(f (+ acc k) (- k 1)))))
(f 0 n)))
Я пытаюсь запустить эти функции в CLISP с входом n = 1000000. Вот результат
[2]> (addup3 1000000)
500000500000
[3]> (addup2 1000000)
*** - Program stack overflow. RESET
Я могу работать как успешно SBCL, но без хвостовой рекурсией один быстрее (только немного, но мне кажется странным). Я просмотрел ответы Stackoverflow для ответов, но не смог найти что-то подобное. Почему я получаю переполнение стека, хотя функция tail-recursive не предназначена для размещения всех вызовов рекурсивных функций в стеке? Должен ли я интерпретировать интерпретатор/компилятор для оптимизации хвостовых вызовов? (Я прочитал что-то вроде (proclaim '(optimize (debug 1)), чтобы установить уровень отладки и оптимизировать за счет возможностей отслеживания, но я не знаю, что это делает). Возможно, ответ очевиден, а код - дерьмо, но я просто не могу понять. Помощь приветствуется.
Редактировать: danlei указал на опечатку, это должен быть вызов addup3 в первой функции, поэтому он является рекурсивным. Если исправлено, как переполнение версии, но не его один
(defun addup (n)
"Adds up the first N integers"
(do ((i 0 (+ i 1))
(sum 0 (+ sum i)))
((> i n) sum)))
Хотя это может быть более типичный способ сделать это, я нахожу странным, что хвостовая рекурсия не всегда оптимизированы, учитывая мои инструкторы хотели сказать мне, что это гораздо более эффективными и простыми.
Как было указано danlei, первая функция имеет опечатку, она должна вызывать себя, а не 'addup', которая по сути является функцией, которую вы описали. Если я исправлю опечатку, она тоже переполнится. Тем не менее, я озадачен тем, что конструкция 'do' более способна, чем рекурсивная. Кажется, я ничего не вижу в отношении TCO для CLISP при поиске в Google и просмотре спецификации на clisp.org. Было бы странно, если бы хвостовая рекурсия была не более мощной, чем обычная рекурсия? – oarfish
Не удивляйтесь. Оптимизация вызовов хвоста просто делает рекурсивное определение выполняемым в пространстве констант (стека), так что оно может быть таким же быстрым, как итеративное определение. Магии не было, что могло бы сделать это быстрее, чем это. – Svante
В Barski's Land of Lisp я просто прочитал, что CLISP только оптимизирует хвостовые вызовы, когда компилируется функция. Фактически, хвост рекурсивный один немного быстрее, так что нет никакой тайны здесь. – oarfish