Мне нравится использовать рекурсию всякий раз, когда я могу, это кажется гораздо более естественным способом петли над чем-то, а не с фактическими циклами. Мне было интересно, есть ли предел рекурсии в lisp? Как и в питоне, где он выстраивается после 1000 циклов? Не могли бы вы использовать его, скажем, в игровом цикле?Есть ли предел рекурсии в lisp?
Тестирование сейчас, простая рекурсивная функция подсчета. Теперь на> 7000000!
Большое спасибо оптимизации
Во-первых, вы должны понимать, что такое хвост.
Хвост - вызов, который не потребляет стек. Теперь вам нужно узнать, когда вы потребляете стек.
Давайте возьмем факторную пример:
(defun factorial (n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
Вот не хвост рекурсивная реализация факториала. Почему? Это связано с тем, что в дополнение к возврату из факториала существует ожидающий вычисления.
(* n ..)
Таким образом, вы укладываете n каждый раз, когда вы вызываете факториал. Теперь давайте напишем хвост рекурсивной факториала:
(defun factorial-opt (n &key (result 1))
(if (= n 1)
result
(factorial-opt (- n 1) :result (* result n))))
Здесь, результат передается в качестве аргумента функции. Итак, вы также потребляете стек, но разница в том, что размер стека остается постоянным. Таким образом, компилятор может оптимизировать его, используя только регистры и оставляя стек пустым.
factorial-opt затем быстрее, но менее читаем. factorial ограничен размером стека factorial-opt нет. Итак, вы должны научиться распознавать функцию хвоста, чтобы знать, ограничена ли рекурсия.
Может быть какая-то техника компилятора для преобразования нерекурсивной функции без хвоста в хвостовую рекурсивную. Может быть, кто-то может указать здесь какую-то ссылку.
В Common Lisp не обязательно верно, что хвостовые вызовы (т. Е. Вызовы в хвостовом положении) не потребляют пространства стека. Это зависит от настроек оптимизации и компилятора. –
, без сомнения, он принял мои факториальные вычисления с 2700 до 3650, но после этого он бросил Stack over flow. Это полезная информация, которую нужно знать. [Другой полезный ответ] (http://stackoverflow.com/questions/15269193/stack-overflow-from-recursive-function-call-in-lisp) – Rorschach
Схема мандатов хвост вызова, а также некоторые реализации CL предлагают его. Однако CL не дает этого.
Обратите внимание, что для оптимизации оптимизации звонка вам необходимо убедиться, что вам не нужно возвращаться. Например. наивная реализация Фибоначчи, в которой есть необходимость возврата и добавления к другому рекурсивному вызову, не будет оптимизирован хвостовой вызов, и в результате у вас не будет пространства стека.
+1 для особого упоминания, что не вся рекурсия - это хвостовой вызов. – Davy8
Не могли бы вы написать мне пример того, чего следует избегать, что бы отрицать хвост? – Isaiah
@ Isaiah: Простая реализация факториала делает: '(defun fact (n) (if (> n 0) (* n (fact (- n 1))) 1))' Причина в том, что умножение выполнено * после * возвращается рекурсивный вызов. –
Наслаждайтесь рекурсией, как наслаждаться молотками. Иногда это лучший инструмент, но если вы хотите вставить винт, потяните за отвертку. – Xach
Мне нравится идея рекурсии. Меня это завораживает. Тем не менее, я бы никогда не использовал его ни в чем коммерческом. Конечно, он упрощает работу с кодом, но за счет эффективности и потребления памяти. Я предпочитаю итеративные версии, чтобы быть в безопасности. –