如何避免Clojure递归函数中的stackoverflow？ [英] How to avoid stackoverflow in clojure recursive function?

问题描述

这里是一个例子：

;; 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。

It produces a StackOverflowError.

推荐答案

这里有几个问题。首先，正如另一个答案所指出的那样，您的标记和筛子函数没有终止条件。看起来它们是设计用于无限序列的，但是如果您传递有限长度的序列，它们将一直走到尽头。

There are a couple of issues here. First, as pointed out in the other answer, your mark and sieve functions don't have terminating conditions. It looks like they are designed to work with infinite sequences, but if you passed a finite-length sequence they'd keep going off the end.

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

The deeper problem here is that it looks like you're trying to have a function create a lazy infinite sequence by recursively calling itself. However, cons is not lazy in any way; it is a pure function call, so the recursive calls to mark and sieve are invoked immediately. Wrapping the outer-most call to sieve in lazy-seq only serves to defer the initial call; it does not make the entire sequence lazy. Instead, each call to cons must be wrapped in its own lazy sequence.

例如：

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

放在一起，这是的实现标记可以对有限序列正确工作，并保留无限序列的惰性。固定筛子留给读者练习。

Putting it together, here's an implementation of mark that works correctly for finite sequences and preserves laziness for infinite sequences. Fixing sieve is left as an exercise for the 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)

这篇关于如何避免Clojure递归函数中的stackoverflow？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！