使用跳板技术解决递归溢出问题

Question

我正试图测试以下分解函数，但对于大的质数它会崩溃：

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

我缺少什么？（我知道这个算法并不完美，改进它完全由我来完成）

- HexedAgain

---

我尝试打印 (println (factors 12424242427)) 的结果，我正常收到了 (12424242427 1)。很奇怪。 - Roman Makhlin

嗯...奇怪，就我所知，我正在使用带有Cider的Emacs（如果这对我可用的堆栈有任何影响的话！？） - HexedAgain

@RomanMakhlin，你使用的是哪个版本的Clojure？我可以在“lein repl”（Clojure 1.6.0）中重现这个错误。 - Charles Duffy

我尝试过版本 1.5.1 和 1.7.0。你能否请尝试从 lein repl 运行你的代码？以防万一。谢谢。 - Roman Makhlin

Answer 1

该死...原来是懒惰的concat函数！！如果您查看堆栈跟踪，大部分工作都与某些懒惰序列（当然还有concat）相关。通过谷歌搜索，我找到了以下内容：

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

然后将我的concat更改为into解决了问题。

- HexedAgain