Desbordamiento al utilizar recur en clojure

Question

Tengo una calculadora de número primo simple en clojure (un algoritmo ineficiente, pero estoy tratando de entender el comportamiento de recurrir por ahora). El código es:

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

Esto funciona siempre que no intente encontrar demasiados números. Por ejemplo

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

funciona. Para cualquier cosa que requiera más recursividad, recibo un error de desbordamiento.

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

no funcionará. En general, si uso recurrir o llamar a primos ingenuos de nuevo sin el intento de TCO no parece hacer ninguna diferencia. ¿Por qué recibo errores para grandes recursiones mientras uso recurre?

Answer 1

recur siempre utiliza recursividad de cola, independientemente de si recurre a un bucle o un cabezal de función. El problema es las llamadas al remove. remove llama al first para obtener el elemento de la secuencia subyacente y comprueba si ese elemento es válido. Si el seq subyacente fue creado por una llamada al remove, recibe otra llamada al first. Si llama al remove 20000 veces en la misma ubicación, llamando al first requiere llamar al first 20000 veces, y ninguna de las llamadas puede ser recursiva de cola. Por lo tanto, el error de desbordamiento de la pila.

Cambio (remove ...) a (doall (remove ...)) corrige el problema, ya que impide el apilamiento infinito de remove llamadas (cada uno se aplica plenamente inmediatamente y devuelve una ss concreto, no un vago ss). Creo que este método solo mantiene una lista de candidatos en la memoria al mismo tiempo, aunque no estoy seguro de esto. Si es así, no es demasiado ineficiente en cuanto a espacio, y un poco de prueba muestra que en realidad no es mucho más lento.