Рекурсивная функция, вызывающая переполнение стека

Question

Я пытаюсь написать простую ситовую функцию для вычисления простых чисел в clojure. Я видел this вопрос о написании эффективной функции решета, но я пока этого не делаю. Сейчас я просто пытаюсь написать очень простое (и медленное) сито. Вот что я придумал:

(defn sieve [potentials primes] 
    (if-let [p (first potentials)] 
    (recur (filter #(not= (mod % p) 0) potentials) (conj primes p)) 
    primes)) 

Для малых диапазонов он работает нормально, но вызывает переполнение стека для больших диапазонов:

user=> (sieve (range 2 30) []) 
[2 3 5 7 11 13 17 19 23 29] 
user=> (sieve (range 2 15000) []) 
java.lang.StackOverflowError (NO_SOURCE_FILE:0) 

Я думал, что с помощью recur это было бы не статическая конструкция цикла? Что мне не хватает?

Answer 1

Вас зовут лень лень filter. Измените (filter ...) на (doall (filter ...)) в вашей форме recur, и проблема должна исчезнуть.

Более углубленное объяснение:

Вызов filter возвращает ленивым SEQ, который материализуется фактические элементы отфильтрованного SEQ по мере необходимости. Как написано, ваш код кладет filter на filter на filter ..., добавив еще один уровень filter ing на каждой итерации; в какой-то момент это взрывается. Решение состоит в том, чтобы заставить весь результат на каждой итерации, чтобы следующий выполнял свою фильтрацию на полностью реализованном seq и возвращал полностью реализованный seq вместо добавления дополнительного слоя ленивой обработки seq; вот что doall.

Answer 2

Алгоритмически проблема заключается в том, что вы продолжаете фильтрацию, когда для нее нет никакой цели. Остановка как можно скорее достичь квадратного снижения глубины рекурсии (sqrt(n) против n):

(defn sieve [potentials primes]  
    (if-let [p (first potentials)] 
     (if (> (* p p) (last potentials)) 
     (concat primes potentials) 
     (recur (filter (fn [n] (not= (mod n p) 0)) potentials) 
       (conj primes p))) 
    primes)) 

Запускается OK для 16,000 (исполняющих всего 30 итераций вместо 1862 г.), и 160000 тоже on ideone. Даже работает на 5% быстрее без doall.