Там предел к рекурсии в шепелявости?
Я люблю использовать рекурсию каждый раз, когда я могу, она походить на намного более естественный способ циклично выполнить по чему-то затем фактические циклы. Я задавался вопросом, существует ли предел рекурсии в шепелявости? Как существует в Python, где он волнуется после как 1 000 циклов? Вы могли использовать его для, говорят, игровой цикл?
Проверение его теперь, простая рекурсивная функция подсчета. Теперь в> 7000000!
Большое спасибо
2 ответа
Сначала следует понять, что такое хвостовой вызов.
Хвостовой вызов - это вызов, который не потребляет стек. Теперь вам нужно распознать, когда вы потребляете стек.
Возьмем пример с факториалом:
(defun factorial (n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
Вот нехвостовая рекурсивная реализация факториала. Почему? Потому что в дополнение к возврату из факториала есть еще и ожидающее вычисление.
(* n ..)
Таким образом, вы складываете n каждый раз, когда вызываете factorial. Теперь давайте напишем хвостовой рекурсивный factorial:
(defun factorial-opt (n &key (result 1))
(if (= n 1)
result
(factorial-opt (- n 1) :result (* result n))))
Здесь результат передается в качестве аргумента функции. Таким образом, вы также расходуете стек, но разница в том, что размер стека остается постоянным. Таким образом, компилятор может оптимизировать его, используя только регистры и оставляя стек пустым.
Тогда factorial-opt работает быстрее, но менее читабелен.
factorial ограничен размером стека, а factorial-opt - нет.
Поэтому следует научиться распознавать хвостовую рекурсивную функцию, чтобы знать, ограничена ли рекурсия.
Возможно, существует какая-то техника компилятора для преобразования не хвостовой рекурсивной функции в хвостовую рекурсивную. Может быть, кто-нибудь укажет здесь какую-нибудь ссылку.
Схема требует оптимизации хвостового вызова, и некоторые реализации CL также предлагают ее. Однако CL не требует этого.
Обратите внимание, что для того, чтобы оптимизация хвостовых вызовов работала, вам нужно убедиться, что вам не нужно возвращаться. Например. наивная реализация Фибоначчи, где есть необходимость вернуться и добавить к другому рекурсивному вызову, не будет оптимизирована для хвостового вызова, и в результате у вас закончится пространство стека.