在clojure中使用循环时溢出

我有一个简单的clojure中的素数计算器（一种低效的算法，但我只是试图了解现在的循环的行为）。代码是：在clojure中使用循环时溢出

(defn divisible [x,y] (= 0 (mod x y))) 

(defn naive-primes [primes candidates] 
    (if (seq candidates) 
     (recur (conj primes (first candidates)) 
       (remove (fn [x] (divisible x (first candidates))) candidates)) 
     primes) 
)

只要我不想找到太多的数字，这个工作。例如

(print (sort (naive-primes [] (range 2 2000))))

的作品。对于需要更多递归的任何事情，我会遇到溢出错误。

(print (sort (naive-primes [] (range 2 20000))))

不起作用。一般来说，无论我是否使用复发或称为天真素数而没有尝试TCO，似乎都没有任何区别。为什么我在使用重复发生时遇到大型递归错误？

来源

2012-02-08 DanB

是否需要循环才能获得尾递归？我在你的代码中看不到循环。我会做出这个答案，但我仍然在学习Clojure。 – octopusgrabbus 2012-02-08 22:42:01

你的代码适用于Clojure 1.2.1和1.3。我发现唯一的错误是当发现质量高达200,000的时候出现'OutOfMemoryError'。 – 2012-02-08 23:02:54

@octopusgrabbus，no，recur也可以以这种方式使用（就在一个函数体内）。请参阅http://clojure.org/special_forms#recur。 – 2012-02-08 23:03:38

recur总是使用尾递归，而不管您是否重复循环或函数头。问题是拨打remove。 remove调用first从底层seq获取元素，并检查该元素是否有效。如果底层seq是通过调用remove创建的，则会再次调用first。如果在同一个seq上调用remove 20000次，则调用first需要调用first 20000次，并且这些调用都不能是尾递归。因此，堆栈溢出错误。

更改(remove ...)到(doall (remove ...))可以解决问题，因为它可以防止的remove呼叫无限层叠（每一个被完全立即应用，并返回一个混凝土SEQ，而不是一个懒惰SEQ）。我认为这种方法一次只能保存一个候选人列表，但我对此并不积极。如果是这样，那么太空间效率不高，而且一些测试表明它实际上并不太慢。

来源

2012-02-08 23:03:54 Retief

谢谢。如果没有你的帮助，它会让我永远不知所措。尽管doall对我来说似乎有点神奇，但这非常有帮助！ – DanB 2012-02-09 02:46:33

在clojure中使用循环时溢出

回答

相关问题