如何避免clojure递归函数中的stackoverflow？

Question

这是一个例子：

;; Helper function for marking multiples of a number as 0
(def mark (fn [[x & xs] k m]
                 (if (= k m) 
                   (cons 0 (mark xs 1       m))
                   (cons x (mark xs (inc k) m))
                   )))

;; Sieve of Eratosthenes
(defn sieve
  [x & xs]
  (if (= x 0)
    (sieve xs)
    (cons x (sieve (mark xs 1 x)))
    ))

(take 10 (lazy-seq (sieve (iterate inc 2))))

它产生了 WhosebugError。

Answer 1

需要终止条件

这里的问题是您的 mark 和 sieve 函数都没有终止条件。必须有一些输入集，每个函数不会为其调用自身，但 return 是一个答案。此外，这些函数的每组（有效）输入最终都应解析为非递归 return 值。

但即使你做对了...

我要补充一点，即使你成功地创建了正确的终止条件，如果递归的深度太大，仍然有可能导致堆栈溢出。这可以通过增加 JVM 堆栈大小在一定程度上缓解，但这有其局限性。

对于某些函数，解决此问题的方法是使用尾调用优化。一些递归函数是 tail recursive，这意味着在其定义中定义的函数的所有递归调用都在 tail call position（是最终的在定义主体中调用的函数）。例如，在 sieve 函数的 (= x 0) 情况下，sieve 是尾调用，因为 sieve 的结果不会传递给任何其他函数。但是，在 (not (= x 0)) 的情况下，调用 sieve 的结果会传递给 cons，因此这不是尾调用。当函数完全尾递归时，可以在幕后将函数定义转换为循环结构，从而避免消耗堆栈。在 clojure 中，这可以通过在函数定义中使用 recur 而不是函数名称来实现（还有一个 loop 结构有时会有帮助）。同样，因为并非所有递归函数都是尾递归的，所以这不是万灵药。但是当他们知道你可以做到这一点时，我会很高兴。

Answer 2

这里有几个问题。首先，正如另一个答案所指出的，您的 mark 和 sieve 函数没有终止条件。看起来它们是为处理无限序列而设计的，但如果你传递一个有限长度的序列，它们就会一直跑到最后。

这里更深层次的问题是，您似乎试图让一个函数通过递归调用自身来创建一个惰性无限序列。但是，cons 一点也不懒惰；这是一个纯函数调用，因此对 mark 和 sieve 的递归调用会立即被调用。在 lazy-seq 中包装对 sieve 的最外层调用仅用于延迟初始调用；它不会使整个序列变得懒惰。相反，对 cons 的每次调用都必须包装在其自己的惰性序列中。

例如：

(defn eager-iterate [f x]
  (cons x (eager-iterate f (f x))))

(take 3 (eager-iterate inc 0)) ; => WhosebugError
(take 3 (lazy-seq (eager-iterate inc 0))) ; => Still a WhosebugError

将此与 iterate 的实际源代码进行比较：

(defn iterate
  "Returns a lazy sequence of x, (f x), (f (f x)) etc. f must be free of side-effects"
  {:added "1.0"
   :static true}
  [f x] (cons x (lazy-seq (iterate f (f x)))))

将它们放在一起，这里是 mark 的一个实现，它可以正确地处理有限序列并保留无限序列的惰性。修复 sieve 留作 reader.

的练习

(defn mark [[x :as xs] k m]
  (lazy-seq
    (when (seq xs)
      (if (= k m)
        (cons 0 (mark (next xs) 1 m))
        (cons x (mark (next xs) (inc k) m))))))

(mark (range 4 14) 1 3)
; => (4 5 0 7 8 0 10 11 0 13)
(take 10 (mark (iterate inc 4) 1 3))
; => (4 5 0 7 8 0 10 11 0 13)

Answer 3

感谢@Alex 的回答，我设法想出了一个可行的懒惰解决方案：

;; Helper function for marking mutiples of a number as 0
(defn mark [[x :as xs] k m]
  (lazy-seq
    (when-not (empty? xs)
      (if (= k m)
        (cons 0 (mark (rest xs) 1 m))
        (cons x (mark (rest xs) (inc k) m))))))


;; Sieve of Eratosthenes
(defn sieve
  [[x :as xs]]
  (lazy-seq
    (when-not (empty? xs)
      (if (= x 0)
        (sieve (rest xs))
        (cons x (sieve (mark (rest xs) 1 x)))))))

有人建议我使用 rest 而不是 next。

如何避免clojure递归函数中的stackoverflow？

How to avoid stackoverflow in clojure recursive function?

stack-overflow

recursion

clojure

需要终止条件

但即使你做对了...