在clojure中使用recur时溢出 [英] Overflow while using recur in clojure

问题描述

我有一个简单的素数计算器在clojure（一个低效的算法，但我只是试图理解recur的行为现在）。代码是：

I have a simple prime number calculator in clojure (an inefficient algorithm, but I'm just trying to understand the behavior of recur for now). The code is:

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

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

This works as long as I am not trying to find too many numbers. For example

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

。对于任何需要更多的递归，我得到一个溢出错误。

works. For anything requiring more recursion, I get an overflow error.

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

将无法工作。一般来说，无论我是否在TCO尝试下再次使用recur或call naive-primes似乎没有任何区别。为什么在使用recur时会出现大型递归的错误？

will not work. In general, whether I use recur or call naive-primes again without the attempt at TCO doesn't appear to make any difference. Why am I getting errors for large recursions while using recur?

推荐答案

recur 始终使用尾递归，无论是循环到循环还是函数头。问题是调用 remove 。 remove 调用首先从底层seq获取元素，并检查该元素是否有效。如果底层seq是通过调用 remove 创建的，则会先调用 。如果在同一seq上调用 remove 20000次，调用首先需要先调用 code> 20000次，并且没有呼叫可以是尾递归。因此，堆栈溢出错误。

recur always uses tail recursion, regardless of whether you are recurring to a loop or a function head. The issue is the calls to remove. remove calls first to get the element from the underlying seq and checks to see if that element is valid. If the underlying seq was created by a call to remove, you get another call to first. If you call remove 20000 times on the same seq, calling first requires calling first 20000 times, and none of the calls can be tail recursive. Hence, the stack overflow error.

将（删除...）更改为（doall（remove ...） ）修复了这个问题，因为它阻止了 remove 调用的无限堆叠（每个调用都会立即完全应用并返回一个具体的seq，而不是一个延迟seq）。我认为这种方法只能一次保存一个候选人列表在记忆中，虽然我不是积极的。如果是这样，它不是太空间低效，并且一点测试表明它实际上不是很慢。

Changing (remove ...) to (doall (remove ...)) fixes the problem, since it prevents the infinite stacking of remove calls (each one gets fully applied immediately and returns a concrete seq, not a lazy seq). I think this method only ever keeps one candidates list in memory at one time, though I am not positive about this. If so, it isn't too space inefficient, and a bit of testing shows that it isn't actually much slower.

这篇关于在clojure中使用recur时溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！