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

Question

我究竟做错了什么？简单的递归几千次调用深度抛出一个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)

Answer 1

这是另一种方式:

(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手动,但在我的经验中并不是那么多.

Answer 2

我理解,堆栈大小取决于您使用的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)))))

Clojure会为此进行尾调优化; 确保你永远不会遇到StackOverflowErrors.

而且由于defn暗示了loop绑定,你可以省略的loop表达,并使用它的参数作为函数的参数.并使其成为1参数函数,使用函数的multiary特征:

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

编辑:对于记录,这里是一个Clojure函数,它返回所有阶乘的延迟序列:

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

Answer 3

Clojure有几种破坏递归的方法

显式尾调用recur.(它们必须是真正的尾调用,所以这不会起作用)

如上所述的懒惰序列.

trampolining你返回一个执行工作而不是直接执行它的函数,然后调用一个trampoline函数,该函数重复调用它的结果,直到它转换为实数而不是函数.

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

记住事实的情况这可以真正缩短堆栈深度,尽管它通常不适用.

ps:我没有对我进行翻译,所以有人会对pitoline事实函数进行测试吗？