Recursion przelewowy użyciu Trampolining

Question

Próbuję przetestować następującą funkcję Faktoryzacji ale to wysadzenie dla dużych liczb pierwszych:

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

który na każdym kroku rekurencyjnego próbuje zmniejszyć liczbę n do jakiegoś produktu p^k m.

Jak rozumiem, trampolina ma rozwiązać problem poprzez powrocie funkcji, które następnie wywołuje trampolina (powrót innej funkcji) i tak dalej, obraz stos patrząc coś takiego:

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

w przeciwieństwie do non-tail rekurencyjne

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

Ale wejście do czynników będąc 12424242427 uzyskać:

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) 

Czego mi brakuje? (Wiem, że ten algorytm nie jest idealny, poprawi to całkowicie dla mnie)

Answer 1

Cholera ... to był leniwy stary konkat !! jeśli spojrzysz na ślad stosu, większość pracy dotyczy pewnej leniwej sekwencji (i oczywiście konkat). Googlowania to wymyśliłem

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

a następnie zmieniając mój concat do into stała się kwestią