Fonction récursive provoquant un débordement de pile

Question

J'essaie d'écrire une fonction simple de tamisage pour calculer les nombres premiers en clojure. J'ai vu ce question sur l'écriture d'une fonction de tamisage efficace, mais je n'en suis pas encore là. Pour l'instant, j'essaie simplement d'écrire un tamis très simple (et lent). Voici ce à quoi j'ai abouti :

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

Pour les petites plages, cela fonctionne bien, mais provoque un dépassement de pile pour les grandes plages :

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)

Je pensais qu'en utilisant recur ce serait une construction en boucle qui ne consomme pas de pile ? Qu'est-ce qui m'échappe ?

Answer 1

Vous êtes frappé par filter de la paresse. Changez (filter ...) a (doall (filter ...)) dans votre recur et le problème devrait disparaître.

Une explication plus approfondie :

L'appel à filter renvoie une seq paresseuse, qui matérialise les éléments réels de la seq filtrée comme requis. Tel qu'il est écrit, votre code empile filter sur filter sur filter ..., ajoutant un niveau supplémentaire de filter à chaque itération ; à un moment donné, cela explose. La solution est de forcer le résultat entier à chaque itération de sorte que la suivante fasse son filtrage sur une seq entièrement réalisée et renvoie une seq entièrement réalisée au lieu d'ajouter une couche supplémentaire de traitement paresseux de la seq ; c'est ce que fait doall lo hace.