Fonction récursive provoquant un débordement de stack

J’essaie d’écrire une simple fonction de tamis pour calculer les nombres premiers dans la structure. J’ai vu cette question sur l’écriture d’une fonction de tamisage efficace, mais je n’en suis pas encore là. En ce moment, j’essaie juste d’écrire un tamis très simple (et lent). Voici ce que j’ai imaginé:

(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ébordement de stack 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 sans consommation de stack? Qu’est-ce que je rate?

Vous êtes touché par la paresse du filter . Changer (filter ...) en (doall (filter ...)) dans votre recur form et le problème devrait disparaître.

Une explication plus approfondie:

L’appel au filter renvoie une séquence paresseuse, qui matérialise les éléments réels de la seq filtrée en fonction des besoins. Tel qu’écrit, votre code emstack le filter sur le filter …, ajoutant un niveau de filter supplémentaire à chaque itération; à un moment donné, cela explose. La solution consiste à forcer le résultat entier à chaque itération afin que le suivant effectue son filtrage sur une seq entièrement réalisée et retourne un seq entièrement réalisé au lieu d’append une couche supplémentaire de traitement seq paresseux; c’est ce doall fait tout le monde.

Algorithmiquement, le problème est que vous continuez à filtrer quand il n’y a plus d’object à cela. L’arrêt le plus tôt possible permet d’obtenir une réduction quadratique de la profondeur de récurrence ( sqrt(n) vs. n ):

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

Fonctionne correctement pour 16 000 (effectuant seulement 30 itérations au lieu de 1862) et 160 000 pour idéone . Même courir 5% plus vite sans le doall .