ricorsione troppo pieno utilizzando trampolino

Question

sto cercando di testare la seguente funzione fattorizzazione ma è far saltare in aria per grandi numeri primi:

(defn divides? [N n] 
    (zero? (mod N n))) 

(defn f-reduce [n f & {:keys [expt] :or {expt 0}}] 
    (if (divides? n f) (f-reduce (/ n f) f :expt (inc expt)) 
        (if (zero? expt) [n []] [n [f expt]]))) 

(defn _factors [n f known-fs] 
    (let [[m fs] (f-reduce n f)] 
    (if (> f (Math/sqrt m)) 
     (cond (and (empty? fs) (= m 1)) known-fs 
      (empty? fs)    (concat known-fs [m 1]) 
      (= m 1)     (concat known-fs [f (last fs)]) 
      true      (concat known-fs [m (last fs)])) 
     #(_factors m (+ 2 f) (concat known-fs fs)))))) 

(defn factors 
    "returns the prime factors of n in form: p_0 expt_0 p_1 expt_1 ... p_m expt_m, 
    where p_i denotes ith prime factor, and expt_i denotes exponent of p_i" 
    [n] 
    (let [[m fs] (f-reduce n 2)] 
    (trampoline (_factors m 3 fs)))) 

che ad ogni passo ricorsivo tenta di ridurre un numero n per qualche prodotto p^k m.

quanto ho capito, trampolino ha lo scopo di risolvere il problema restituendo una funzione che trampolino chiama poi (tornare un'altra funzione) e così via, la qualcosa immagine di stack che sembra:

|fn 1| --> |fn 2| -- ... --> |fn n| 

in contrasto con la non coda ricorsiva

|fn 1| --> |fn 1|fn 2| -- .. --> |fn 1|fn 2| ... |fn n-k| BOOM| 

Ma per un ingresso a fattori essendo 12.424.242,427 mila ottengo:

java.lang.StackOverflowError: null 
at clojure.lang.LazySeq.seq (LazySeq.java:49) 
    clojure.lang.RT.seq (RT.java:507) 
    clojure.core/seq (core.clj:137) 
    clojure.core$concat$fn__4215.invoke (core.clj:691) 
    clojure.lang.LazySeq.sval (LazySeq.java:40) 
    clojure.lang.LazySeq.seq (LazySeq.java:49) 
    clojure.lang.RT.seq (RT.java:507) 
    clojure.core/seq (core.clj:137) 
    clojure.core$concat$fn__4215.invoke (core.clj:691) 
    clojure.lang.LazySeq.sval (LazySeq.java:40) 
    clojure.lang.LazySeq.seq (LazySeq.java:49) 
    clojure.lang.RT.seq (RT.java:507) 
    clojure.core/seq (core.clj:137) 
    clojure.core$concat$fn__4215.invoke (core.clj:691) 
    clojure.lang.LazySeq.sval (LazySeq.java:40) 
    clojure.lang.LazySeq.seq (LazySeq.java:49) 
    clojure.lang.RT.seq (RT.java:507) 
    clojure.core/seq (core.clj:137) 
    clojure.core$concat$fn__4215.invoke (core.clj:691) 
    clojure.lang.LazySeq.sval (LazySeq.java:40) 
    clojure.lang.LazySeq.seq (LazySeq.java:49) 

Cosa mi manca? (So ​​che questo algoritmo non è perfetto, il miglioramento è uno solo per me)

Answer 1

Dannazione ... era pigro vecchio concat !! se si guarda la traccia dello stack, la maggior parte del lavoro riguarda una sequenza pigra (e naturalmente concat). Googling questo mi si avvicinò con

http://stuartsierra.com/2015/04/26/clojure-donts-concat

e poi cambiando il mio concat-into risolto il problema