Overflow durante l'utilizzo ricorrente in clojure

Question

Ho un semplice calcolatore di numeri primi in clojure (un algoritmo inefficiente, ma sto solo cercando di capire il comportamento di recur per ora). Il codice è:

(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) 
) 

Questo funziona fintanto che non sto cercando di trovare troppi numeri. Ad esempio

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

opere. Per qualsiasi cosa richieda più ricorsione, ottengo un errore di overflow.

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

non funziona. In generale, se ricorrere o chiamare di nuovo i primati naive senza il tentativo di TCO non sembra fare alcuna differenza. Perché ricevo errori per ricorsioni di grandi dimensioni durante l'utilizzo di ricorrenza?

Answer 1

recur utilizza sempre la ricorsione della coda, indipendentemente dal fatto che si stia ricorrendo a un ciclo oa una testa di funzione. Il problema sono le chiamate a remove. remove chiama first per ottenere l'elemento dal seq sottostante e controlla se quell'elemento è valido. Se il seq sottostante è stato creato da una chiamata a remove, si ottiene un'altra chiamata a first. Se si chiama remove 20000 volte sullo stesso seq, chiamare first richiede chiamare first 20000 volte e nessuna delle chiamate può essere ricorsiva in coda. Quindi, l'errore di overflow dello stack.

Modifica (remove ...) a (doall (remove ...)) risolve il problema, in quanto impedisce l'impilamento infinito di remove chiamate (ognuno viene completamente applicata immediatamente e restituisce una seq concreto, non un seq pigro). Penso che questo metodo mantenga sempre una lista di candidati in memoria in una sola volta, anche se non ne sono certo. Se è così, non è troppo poco efficiente, e un po 'di test mostra che non è in realtà molto più lento.