Есть ли предел рекурсии в lisp? - PullRequest
Новая
       10

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

12 голосов
/ 08 июня 2010

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

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

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

Ответы [ 2 ]

11 голосов
/ 08 июня 2010

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

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

9 голосов
/ 08 июня 2010

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

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

Давайте рассмотрим пример фактора: 

(defun factorial (n)
    (if (= n 1)
        1
        (* n (factorial (- n 1)))))

Вот нехвостовая рекурсивная реализация факториала. Зачем? Это связано с тем, что в дополнение к возврату из факториала есть ожидающие вычисления. 

(* n ..)

Таким образом, вы складываете n каждый раз, когда вызываете factorial. Теперь давайте напишем хвостовой рекурсивный факториал: 

(defun factorial-opt (n &key (result 1))
    (if (= n 1)
        result
        (factorial-opt (- n 1) :result (* result n))))

Здесь результат передается в качестве аргумента функции. Таким образом, вы также потребляете стек, но разница в том, что размер стека остается постоянным. Таким образом, компилятор может оптимизировать его, используя только регистры и оставляя стек пустым.

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

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

...