Rekursion Überlauf mit trampolining

Question

Ich versuche, die folgende Faktorisierung Funktion zu testen, aber es ist für große Primzahlen Sprengung:

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

, die bei jedem rekursiven Schritt p^k m eine Reihe n zu einem gewissen Produkt zu reduzieren versucht.

Wie ich verstehe, ist Trampolin gemeint Problem zu lösen, indem eine Funktion zurückkehrt, das Trampolin ruft dann (immer eine andere Funktion zurück) und so weiter, um den Stapel Bild sucht so etwas wie:

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

im Gegensatz zu dem nicht-Schwanz rekursive

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

Aber für eine Eingabe an Faktoren 12424242427 zu sein, erhalte ich:

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) 

Was fehlt mir? (Ich weiß, dass dieser Algorithmus nicht perfekt ist, die Verbesserung ist eine vollkommen für mich)

Answer 1

Verdammt ... es war faule alte concat !! Wenn Sie sich die Stack-Spur anschauen, gehört die meiste Arbeit zu einer gewissen Lazy-Sequenz (und natürlich zu Concat). Googeln diese kam ich mit

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

und dann in der Regel das Problem behoben meine concat-into Wechsel