Recursion tràn sử dụng trampolining

Question

Tôi đang cố gắng để kiểm tra chức năng phân tích nhân tử sau nhưng nó thổi lên cho số nguyên tố lớn:

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

mà ở mỗi bước đệ quy nỗ lực để giảm bớt một số n đối với một số sản phẩm p^k m.

Theo tôi được biết, tấm bạt lò xo có nghĩa là để giải quyết vấn đề bằng cách quay một chức năng mà tấm bạt lò xo sau đó gọi (nhận lại chức năng khác) và như vậy, một cái gì đó ngăn xếp hình ảnh trông như:

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

như trái ngược với không đệ quy đuôi

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

Nhưng đối với một đầu vào các yếu tố là 12424242427 tôi nhận được:

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) 

Tôi đang thiếu gì? (Tôi biết thuật toán này không hoàn hảo, cải thiện đó là một thuật toán hoàn toàn đối với tôi)

Answer 1

Chết tiệt ... đó là bản concat cũ lười biếng !! nếu bạn nhìn vào dấu vết ngăn xếp hầu hết các công việc liên quan đến một số trình tự lười biếng (và tất nhiên concat). Googling này tôi đã đưa ra

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

và sau đó thay đổi của tôi concat-into khắc phục sự cố