Clojure的：简单的阶乘导致堆栈溢出(Clojure: Simple factorial cau

2019-09-15 04:17发布

站内文章 / 后端开发

36 0

别忘想泡老子

女 | 书童

私信

我究竟做错了什么？简单而又重复几千电话深抛出一个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:

堆栈大小，我明白了，取决于你所使用的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的会做这个尾调用优化; 确保你永远不会遇到StackOverflowError秒。

而且由于defn意味着loop结合，你可以省略loop的表达，并使用它的参数作为函数的参数。并使其成为1个参数功能，使用了multiary的功能caracteristic ：

(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 2:

这里的另一种方式：

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

这会不会吹堆栈，因为range返回一个懒惰的序列，并reduce整个序列散步而不握住头。

reduce利用分块seqs如果可以的，所以这实际上可以进行比使用更好的recur自己。使用悉达多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 3:

Clojure的有破坏递归的几种方法

明确的尾部易复发调用。（他们必须忠实地尾调用所以这不会工作）

如上所述懒惰序列。

蹦床在那里你返回做的工作，而不是直接做它的函数，然后调用蹦床函数，直到地调成真正的价值，而不是一个函数，重复调用它的结果。

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

memoizing事实的情况下，这个真的可以缩短栈深度，虽然它不是普遍适用。

PS：我没有对我有这样REPL会有人好心的测试解决trapoline事实功能？

Answer 4:

当我正要张贴下面，我看到它是几乎一样的方案例如张贴JasonTrue ......总之，这里的Clojure中的实现：

user=> (defn fact[x]
        ((fn [n so_far]
          (if (<= n 1)
              so_far
              (recur (dec n) (* so_far n)))) x 1))
#'user/fact
user=> (fact 0)
1
user=> (fact 1)
1
user=> (fact 2)
2
user=> (fact 3)
6
user=> (fact 4)
24
user=> (fact 5)
120

等等

Answer 5:

作为l0st3d建议，可以考虑使用易复发或懒惰序列。

另外，尽量使你的序列懒使用内置序列的形式作为反对直接做建筑的。

下面是使用内置的序列的形式来创建一个懒惰的斐波那契序列（从编程Clojure的书）的一个例子：

(defn fibo []
  (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))

=> (take 5 (fibo))
(0 1 1 2 3)

Answer 6:

堆栈深度是一个小烦恼（尚未配置），但即使在像计划或F＃你最终与你的代码运行的堆栈空间尾递归的语言。

据我所知，你的代码是不可能被尾递归在支持尾递归透明的环境中，即使进行了优化。你想看看一个延续传递风格，以尽量减少堆栈深度。

下面是计划从典型的例子维基百科，这可以转换为Clojure中，F＃或没有太多的麻烦另一种功能性的语言：

(define factorial
  (lambda (n)
      (let fact ([i n] [acc 1])
        (if (zero? i)
            acc
            (fact (- i 1) (* acc i))))))

Answer 7:

另外，简单的递归实现简单的可能是这样的：

(defn fac [x]
    "Returns the factorial of x"
    (if-not (zero? x) (* x (fac (- x 1))) 1))

Answer 8:

为了增加悉达多雷迪的答案，你也可以借用阶乘函数形式计算机程序的构造和解释，有一些具体的Clojure-调整。这给了我相当不错的表现即使是非常大的阶乘计算。

(defn fac [n]
  ((fn [product counter max-count]
     (if (> counter max-count)
         product
         (recur (apply *' [counter product])
                (inc counter)
                max-count)))
   1 1 n))