recursion - recursión - recursividad javascript ejemplos

Función recursiva que causa un desbordamiento de la pila

Question

Estoy tratando de escribir una función de criba simple para calcular números primos en clojure. He visto this pregunta sobre cómo escribir una función de tamiz eficiente, pero todavía no llegué a ese punto. En este momento solo intento escribir un tamiz muy simple (y lento). Esto es lo que se me ocurrió:

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

Para rangos pequeños funciona bien, pero causa un desbordamiento de pila para rangos grandes:

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)

Pensé que al recur esto sería una construcción de bucle que no consume pila ¿Qué me estoy perdiendo?

Answer 1

Algorítmicamente, el problema es que continúas filtrando cuando ya no hay más propósito. Al detenerse tan pronto como sea posible se logra una reducción cuadrática en la profundidad de recursión ( 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))

Funciona bien para 16,000 (realizando solo 30 iteraciones en lugar de 1862), y para 160,000 también, en ideone . Incluso funciona un 5% más rápido sin el doall .

Answer 2

Estás siendo golpeado por la pereza del filter . Cambiar (filter ...) a (doall (filter ...)) en su formulario recur y el problema debería desaparecer.

Una explicación más profunda:

La llamada al filter devuelve un seq perezoso, que materializa los elementos reales del seq filtrado según sea necesario. Como está escrito, las pilas de códigos filter filter tras filter ..., agregando un nivel más de filter en cada iteración; en algún momento esto explota. La solución es forzar el resultado completo en cada iteración para que el siguiente haga su filtrado en un seq completamente realizado y devuelva un seq completamente realizado en lugar de agregar una capa extra de procesamiento de seq perezoso; eso es lo que hacen todos.