导致堆栈溢出的递归函数 [英] 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?

推荐答案

您正被 filter 的懒惰所打击.将 (filter ...) 更改为 (doall (filter ...)) 在您的 recur 表单中，问题应该会消失.

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

更深入的解释:

对 filter 的调用返回一个惰性序列，它根据需要具体化过滤序列的实际元素.如所写，您的代码将 filter 叠加在 filter 上，filter... 上，再添加一层 filtering在每次迭代中；在某些时候这会爆炸.解决方案是在每次迭代时强制执行整个结果，以便下一次对完全实现的 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屋！