Wann die reine Rekursion und wann die Schleife/Wiederholung verwendet werden soll?

"pure Rekursion" ist eine erfundene Bezeichnung hier, bitte verzeihen Sie.Wann die reine Rekursion und wann die Schleife/Wiederholung verwendet werden soll?

Hier sind zwei Beispiele zwei verschiedene Rekursion Ansätze. Was sind die Richtlinien für die Verwendung von einem über einen anderen?

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

Quelle

2013-01-11 Yuriy Zubarev

Ich verstehe wirklich nicht, welche Richtlinien Sie sprechen. Sie könnten im ersten Beispiel einfach nicht ** Loop/Recurve ** wählen, weil 'take-while' nicht in der ** tail-position ** verwendet wird. Was ist das Problem? ** Loop/recur ** ist immer besser, wenn es als Funktion Rekursionsanruf verwendet werden könnte und @mikera erklärt warum. – hsestupin

einige Faktoren zu berücksichtigen:

Schleife/recur Stapelspeicher nicht verbraucht - so ist es die richtige Wahl, wenn Sie gehen tief verschachtelte Rekursion zu tun, die sonst verursachen könnten StackOverflowError
Schleife/recur ist schneller - es ist eines der effizientesten Konstrukte in Clojure, es richtig gemacht sollte die Geschwindigkeit eines äquivalenten for-Schleife in Java-Code übereinstimmen
normale Rekursion ist mehr idiomatische - im Durchschnitt neigt es Ihnen klarer, funktionalen Code zu geben, während Schleife/recur neigt man eher auf einen Imperativ, iterativen Stil
Schleife/recur weitere Einschränkungen hat drücken - Sie kann nur in Schwanz Position wieder auftreten, können Sie die gegenseitige Rekursion zwischen zwei verschiedenen Funktionen, die nicht tun, etc. Manchmal einfach ist es nicht möglich, ist eine Schleife/recur Arbeit, zu anderen Zeiten machen Sie müssen Ihren Code verziehen, dies zu tun.

Quelle

2013-01-11 06:04:01 mikera

Wäre es nicht möglich sein, dass der Compiler oben idiomatische Rekursion von der Form, in Abzug während zu transformieren (wobei die Rekursion letzte ist) in die Schleife/wiederholt Form (oder den Code für die Schleife erzeugt/wiederholen Form)? – Hendekagon

@Hendekagon: Nicht in diesem Fall, weil die Rekursion nicht in Endposition ist. Theoretisch könnte es in anderen Situationen passieren, aber ich glaube, es war eine Design-Entscheidung von Rich Hickey, dies nicht automatisch zu tun - wenn Sie also eine Tail-Rekursion wollen, müssen Sie explizit mit 'recur' danach fragen – mikera

Der einzige Grund lazy-seq/lazy-cons Mechanismus zu verwenden, erzeugt lazy Sequenzen. Wenn Sie sie nicht brauchen, dann sollte loop/recur zweifellos verwendet werden.

Quelle

2013-01-11 07:23:46 mobyte

Verwenden Ebene Rekursion, wenn Sie Ihre Funktion in erster Linie schreiben. Dann ändern Sie dies, um zu wiederholen, sobald Sie alles funktioniert haben, wenn Sie können.

Ein Problem bei der TCO ist, dass, wenn Sie Ihre Rekursion sträuben, du einen unendlichen Blick erhalten. Ohne, stürzt Ihr Code gut mit einem Stack-Überlauf ab, was Sie wollen. Ich mochte die Idee des Rezidivs nicht, als ich das erste Mal davon hörte - die meisten Optimierungen sollten einfach passieren - aber es ist nett, es ausschalten zu können.

Quelle

2013-01-11 10:16:02

Wann die reine Rekursion und wann die Schleife/Wiederholung verwendet werden soll?

Antwort

Verwandte Themen