Trampoline recursion overflow

Question

I am trying to check the following factorization function, but it explodes for large prime numbers:

(defn divides? [N n] (zero? (mod N n))) (defn f-reduce [nf & {:keys [expt] :or {expt 0}}] (if (divides? nf) (f-reduce (/ nf) f :expt (inc expt)) (if (zero? expt) [n []] [n [f expt]]))) (defn _factors [nf known-fs] (let [[m fs] (f-reduce nf)] (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)))) 

which at each recursive step tries to reduce the number n to some product p^km .

As I understand it, the trampoline is designed to solve the problem by returning the function that the trampoline then calls (returning another function), etc., the stack image looks something like this:

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

unlike irregular recursive

 |fn 1| --> |fn 1|fn 2| -- .. --> |fn 1|fn 2| ... |fn nk| BOOM| 

But for input for coefficients 12424242427 I get:

 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) 

What am I missing? (I know that this algorithm is not perfect, it improves, which is completely for me)

Answer 1

Damn ... it was a lazy old concat! if you look at the stack trace, most of the work relates to some lazy sequence (and, of course, concat). In this article I came up with

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

and then changing my concat to into , fixed the problem