recursion - 如何避免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))))

它会产生 StackOverflowError。

Answer 1

这里有几个问题。首先，正如另一个答案所指出的，您的 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)) ; => StackOverflowError
(take 3 (lazy-seq (eager-iterate inc 0))) ; => Still a StackOverflowError

将此与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 留给读者作为练习。

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