Есть ли предел рекурсии в lisp?

Мне нравится использовать рекурсию всякий раз, когда я могу, кажется, что это гораздо более естественный способ перебрать что-то, а не фактические циклы. Мне было интересно, есть ли предел рекурсии в lisp? Как и в питоне, где он выстраивается после 1000 циклов? Не могли бы вы использовать его, скажем, в игровом цикле?

Тестирование теперь, простая рекурсивная функция подсчета. Теперь нa > 7000000!

Спасибо большое

Ответы

Ответ 1

Сначала вы должны понять, что такое хвостовой вызов.

Хвост - вызов, который не потребляет стек. Теперь вам нужно узнать, когда вы потребляете стек.

Возьмем факториальный пример:

(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 - нет. Поэтому вы должны научиться распознавать функцию хвоста в другом, чтобы знать, ограничена ли рекурсия.

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

Ответ 2

Схема требует оптимизации хвостового вызова, и некоторые реализации CL также предлагают ее. Однако CL не дает этого.

Обратите внимание, что для оптимизации оптимизации звонков вам нужно убедиться, что вам не нужно возвращаться. Например. наивная реализация Фибоначчи, где есть необходимость возврата и добавления к другому рекурсивному вызову, не будет оптимизирован хвостовой вызов, и в результате у вас закончится пространство стека.