递归函数导致堆栈溢出 [英] Recursive function causing a stack overflow

问题描述

我想写一个简单的筛选函数来计算clojure中的素数。我看到关于编写高效筛选函数的这个问题，但我没有到那一点。现在我只是试图写一个非常简单（和慢）筛。这是我想出了：

I am trying to write a simple sieve function to calculate prime numbers in clojure. I've seen this question about writing an efficient sieve function, but I am not to that point yet. Right now I am just trying to write a very simple (and slow) sieve. Here is what I have come up with:

(defn sieve [potentials primes]
  (if-let [p (first potentials)]
    (recur (filter #(not= (mod % p) 0) potentials) (conj primes p))
    primes))

对于小范围，它工作正常，但会导致大范围的堆栈溢出：

For small ranges it works fine, but causes a stack overflow for large ranges:

user=> (sieve (range 2 30) [])
[2 3 5 7 11 13 17 19 23 29]
user=> (sieve (range 2 15000) [])
java.lang.StackOverflowError (NO_SOURCE_FILE:0)

我想通过使用 recur 这将是一个非堆栈消耗循环结构？

I thought that by using recur this would be a non-stack-consuming looping construct? What am I missing?

推荐答案

您将被过滤器懒惰。在（过滤器...）到（doall（过滤器...）） >

You're being hit by filter's laziness. Change (filter ...) to (doall (filter ...)) in your recur form and the problem should go away.

更深入的解释：

调用 filter 返回一个延迟序列，它根据需要实现过滤序列的实际元素。如下：过滤过滤过滤过滤 ...，在每次迭代中添加一个级别的过滤器在某一点上，这爆炸了。解决方案是在每次迭代时强制整个结果，以便下一个将在完全实现的seq上进行其过滤，并返回完全实现的seq，而不是添加额外的延迟seq处理层;这是 doall 的作用。

The call to filter returns a lazy seq, which materialises actual elements of the filtered seq as required. As written, your code stacks filter upon filter upon filter..., adding one more level of filtering at each iteration; at some point this blows up. The solution is to force the whole result at each iteration so that the next one will do its filtering on a fully realised seq and return a fully realised seq instead of adding an extra layer of lazy seq processing; that's what doall does.

这篇关于递归函数导致堆栈溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！