当前位置:  开发笔记 > 编程语言 > 正文

使用trampolining进行递归溢出

如何解决《使用trampolining进行递归溢出》经验,为你挑选了0个好方法。

我正在尝试测试以下因子分解函数,但它正在为大量素数爆发:

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

我错过了什么?(我知道这个算法并不完美,改进完全适合我)

推荐阅读
拾味湖
这个屌丝很懒,什么也没留下!
DevBox开发工具箱 | 专业的在线开发工具网站    京公网安备 11010802040832号  |  京ICP备19059560号-6
Copyright © 1998 - 2020 DevBox.CN. All Rights Reserved devBox.cn 开发工具箱 版权所有