Recursion overflow using trampolining

Question

I'm trying to test the following factorisation function but it's blowing up for large primes:

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

which at each recursive step attempts to reduce a number n to some product p^k m.

As I understand, trampoline is meant to solve problem by returning a function which trampoline then calls (getting back another function) and so on, the stack picture looking something like:

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

as opposed to the non-tail recursive

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

But for an input to factors being 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 this algorithm isn't perfect, improving that is one entirely for me)

Answer 1

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

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

and then changing my concat to into fixed the issue