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

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

(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 это будет нециклическая конструкция цикла? Что мне не хватает?

Ответ 1

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

Более подробное объяснение:

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

Ответ 2

Алгоритмически проблема заключается в том, что вы продолжаете фильтрацию, когда нет никакой цели. Остановка как можно раньше достигает квадратичного уменьшения глубины рекурсии (sqrt(n) vs. 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), а также для 160 000, на ideone. Даже работает на 5% быстрее без doall.