何時使用純遞歸以及何時使用循環/重複？

以下是使用兩種不同遞歸方法的兩個示例。相互使用的準則是什麼？

(defn take-while 
    "Returns a lazy sequence of successive items from coll while 
    (pred item) returns true. pred must be free of side-effects." 
    {:added "1.0" 
    :static true} 
    [pred coll] 
    (lazy-seq 
    (when-let [s (seq coll)] 
     (when (pred (first s)) 
     (cons (first s) (take-while pred (rest s))))))) 

(defn take-last 
    "Returns a seq of the last n items in coll. Depending on the type 
    of coll may be no better than linear time. For vectors, see also subvec." 
    {:added "1.1" 
    :static true} 
    [n coll] 
    (loop [s (seq coll), lead (seq (drop n coll))] 
    (if lead 
     (recur (next s) (next lead)) 
     s)))

來源

2013-01-11 Yuriy Zubarev

我真的不明白你在說什麼指導方針。在第一個例子中，你根本無法選擇** loop/recur **方法，因爲'take-while'不是用在** tail-position **中。問題是什麼？ **循環/重複**總是更好，如果它可以使用比函數遞歸調用和@mikera解釋了原因。 – hsestupin

幾個因素需要考慮：

環/易復發不佔用堆棧空間 - 所以這是一個正確的選擇，如果你打算做深度嵌套的遞歸否則可能導致StackOverflowError
環/易復發更快 - 這是Clojure中最有效的結構之一，正確地完成它應該匹配同等的速度循環在Java代碼中
正常遞歸是更地道 - 平均這會給你更清晰，功能更強大的代碼，而環/易復發往往更推動你走向一個勢在必行的，迭代式的
環/易復發有更多的限制 - 你只能在尾部位置重複出現，不能在兩個不同的函數之間進行相互遞歸等。有時，不可能使循環/重複工作成爲可能，而在其他時候，您可能需要扭曲代碼才能這樣做。

來源

2013-01-11 06:04:01 mikera

編譯器不可能將上面的take-while（遞歸是最後一個）中的形式的慣用遞歸轉換爲循環/遞歸形式（或者它爲循環/遞歸形式生成的代碼）？ – Hendekagon

@Hendekagon：不是在這種情況下，因爲遞歸不在尾部位置。理論上它可能在其他情況下，但我相信這是Rich Hickey設計決定不自動執行此操作 - 所以如果您想要尾遞歸，則必須使用'recur' – mikera

使用lazy-seq/lazy-cons機制的唯一原因是生成惰性序列。如果你不需要它們，那麼毫無疑問應該使用loop/recur。

來源

2013-01-11 07:23:46 mobyte

當您首先編寫函數時使用簡單遞歸。如果可以的話，一旦你有所有的工作，然後改變它以重演。

總擁有成本的一個問題是，如果你拒絕你的遞歸，你會得到一個無限的外觀。沒有，你的代碼會很好地崩潰，這是你想要的。當我第一次聽說它時，我不喜歡這種復發的想法 - 大部分優化都應該發生 - 但能夠關閉它是件好事。

來源

2013-01-11 10:16:02

何時使用純遞歸以及何時使用循環/重複？

回答

相關問題