在clojure中使用recur时溢出

Question

我在clojure中有一个简单的素数计算器(一种效率低下的算法,但我现在只想了解recur的行为).代码是:

(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的情况下再次使用复发或再次调用naive-primes似乎没有任何区别.为什么我在使用recur时遇到大型递归错误？

Answer 1

recur始终使用尾递归,无论您是重复循环还是函数头.问题是打电话给remove. remove调用first从底层seq获取元素并检查该元素是否有效.如果底层seq是通过调用创建的remove,则会再次调用first.如果remove在同一个seq上调用20000次,则调用first需要调用first20000次,并且所有调用都不能进行尾递归.因此,堆栈溢出错误.

更改(remove ...)以(doall (remove ...))解决问题,因为它可以防止无限堆叠remove调用(每个调用立即完全应用并返回具体的seq,而不是lazy seq).我认为这种方法一次只能将一个候选列表保留在内存中,尽管我对此并不乐观.如果是这样,它的空间效率不会太低,而且一些测试表明它实际上并不慢.