我正在尝试测试以下因子分解函数,但它正在为大量素数爆发:
(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))))
在每个递归步骤中尝试将数字减少n
到某个产品p^k m
.
据我所知,trampoline是通过返回一个函数来解决问题,该函数然后调用trampoline(获取另一个函数)等等,堆栈图片看起来像:
|fn 1| --> |fn 2| -- ... --> |fn n|
而不是非尾递归
|fn 1| --> |fn 1|fn 2| -- .. --> |fn 1|fn 2| ... |fn n-k| BOOM|
但是对于因素的输入是12424242427我得到:
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)
我错过了什么?(我知道这个算法并不完美,改进完全适合我)