Clojure:简单的阶乘导致堆栈溢出

我究竟做错了什么？简单的递归几千次调用深度抛出一个StackOverflowError.

如果Clojure递归的限制如此之低,我该如何依赖它？

(defn fact[x]
  (if (<= x 1) 1 (* x  (fact (- x 1))  )))

user=> (fact 2)
2

user=> (fact 4)
24

user=> (fact 4000)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)

Brian Carper.. 75

这是另一种方式:

(defn factorial [n]
  (reduce * (range 1 (inc n))))

这不会打击堆栈因为range返回一个懒惰的seq,并且reduce在没有抓住头部的情况下穿过seq.

reduce如果可以的话,可以使用chunked seqs,所以这实际上比使用recur自己更好.使用基于Siddhartha Reddy的 recur版本和reduce基于此版本:

user> (time (do (factorial-recur 20000) nil))
"Elapsed time: 2905.910426 msecs"
nil
user> (time (do (factorial-reduce 20000) nil))
"Elapsed time: 2647.277182 msecs"
nil

只是略有不同.我喜欢我的离开recur环map和reduce朋友,这是更具可读性和明确,并使用recur内部多一点优雅的比我可能做手工.有些时候你需要recur手动,但在我的经验中并不是那么多.

这是另一种方式:

(defn factorial [n]
  (reduce * (range 1 (inc n))))

这不会打击堆栈因为range返回一个懒惰的seq,并且reduce在没有抓住头部的情况下穿过seq.

reduce如果可以的话,可以使用chunked seqs,所以这实际上比使用recur自己更好.使用基于Siddhartha Reddy的 recur版本和reduce基于此版本:

user> (time (do (factorial-recur 20000) nil))
"Elapsed time: 2905.910426 msecs"
nil
user> (time (do (factorial-reduce 20000) nil))
"Elapsed time: 2647.277182 msecs"
nil

只是略有不同.我喜欢我的离开recur环map和reduce朋友,这是更具可读性和明确,并使用recur内部多一点优雅的比我可能做手工.有些时候你需要recur手动,但在我的经验中并不是那么多.

我理解,堆栈大小取决于您使用的JVM以及平台.如果您使用的是Sun JVM,则可以使用-Xss和-XThreadStackSize参数来设置堆栈大小.

在Clojure中进行递归的首选方法是使用loop/ recur:

(defn fact [x]
    (loop [n x f 1]
        (if (= n 1)
            f
            (recur (dec n) (* f n)))))

(defn fact
  ([n] (fact n 1))
  ([n f]
  (if (<= n 1)
    f
    (recur (dec n) (* f n)))))

(defn factorials []
    (letfn [(factorial-seq [n fact]
                           (lazy-seq
                             (cons fact (factorial-seq (inc n) (* (inc n) fact)))))]
      (factorial-seq 1 1)))

(take 5 (factorials)) ; will return (1 2 6 24 120)

(defn fact ([x] (trampoline (fact (dec x) x))) 
           ([x a] (if (<= x 1) a #(fact (dec x) (*' x a)))))
(fact 42)
620448401733239439360000N