Переполнение при использовании recur в clojure

Question

У меня есть простой калькулятор простых чисел в clojure (неэффективный алгоритм, но я просто сейчас пытаюсь понять поведение повторения).Код:

(defn divisible [x,y] (= 0 (mod x y)))

(defn naive-primes [primes candidates] 
  (if (seq candidates)
      (recur  (conj primes (first candidates)) 
              (remove (fn [x] (divisible x (first candidates))) candidates))
      primes)
)

Это работает до тех пор, пока я не пытаюсь найти слишком много чисел.Например

(print (sort (naive-primes [] (range 2 2000))))

работает.Для чего-либо, требующего больше рекурсии, я получаю ошибку переполнения.

    (print (sort (naive-primes [] (range 2 20000))))

не будет работать.В общем, то, что я использую recur или вызываю naive-primes снова без попытки TCO, не имеет никакого значения.Почему я получаю ошибки для больших рекурсий при использовании recur?

Answer 1

recur всегда использует хвостовую рекурсию, независимо от того, возвращаетесь ли вы в цикл или в заголовок функции. Проблема в звонках на remove. remove вызывает first, чтобы получить элемент из нижележащего seq, и проверяет, является ли этот элемент допустимым. Если базовый seq был создан при вызове remove, вы получаете еще один вызов first. Если вы вызываете remove 20000 раз в течение одного и того же сеанса, для вызова first требуется вызов first 20000 раз, и ни один из вызовов не может быть хвостовым рекурсивным. Следовательно, ошибка переполнения стека.

Изменение (remove ...) на (doall (remove ...)) устраняет проблему, поскольку предотвращает бесконечное суммирование вызовов remove (каждый из них сразу же полностью применяется и возвращает конкретный, а не ленивый). Я думаю, что этот метод хранит только один список кандидатов в памяти одновременно, хотя я не уверен в этом. Если это так, это не слишком неэффективно, и небольшое количество тестов показывает, что на самом деле это не намного медленнее.