Sind rekursive Funktionen übersichtlicher?
-
Cyres schrieb:
Aber nehmen wir doch von oben das Fib-Beispiel. Es gibt drei Implementationsmöglichkeiten:
- trivial: einfach die Formel benutzen
- dynamisch: alle Zwischenergebnisse speichern
- fast: nur die letzten beiden Ergebnisse speichern
Und dann gibt es noch echt schnell mit square-and-multiply...
-
Eigentlich sind rekursive Funktionen doch fast immer schlechter zu lesen, außer wenn man sie schon von Grund auf immer rekursiv formuliert werden. Warum sollte man irgendwas rekursiv hinschreiben, wenn es normal nie so gemacht wird?
-
Ja genauso wie
std::accumulate,std::find_if,std::min_element, ... schlechter lesbar sind als die zugehoerigen for-Schleifen.
Es gibt Unterschiede zwischen expliziter Rekursion und fold_left/fold_rightoder andere Rekursionschema. Ersteres ist schwerer als letzteres.
-
Wer rekursiv programmiert und foldr/l nicht versteht, hat auch irgendwas falsch gemacht
-
knivil schrieb:
Ja genauso wie
std::accumulate,std::find_if,std::min_element, ... schlechter lesbar sind als die zugehoerigen for-Schleifen.Ohne c++11 waren std::find_if und co auf jeden fall schlecher lesbar, mal schauen, obs mit c++11 besser wird.
-
Cyres schrieb:
Wer rekursiv programmiert und foldr/l nicht versteht, hat auch irgendwas falsch gemacht
absoluter blödsinn, das kenntnisse von foldr/l für viele sprachen völlig irrelevant!
-
lolz0r schrieb:
Cyres schrieb:
Wer rekursiv programmiert und foldr/l nicht versteht, hat auch irgendwas falsch gemacht
absoluter blödsinn, das kenntnisse von foldr/l für viele sprachen völlig irrelevant!
Nicht, wenn du ausschließlich funktional programmierst. Klar kann man folds mit Schleifen ersetzen (zum Glück), aber ohne Schleifen wird das ein einsamer Krampf...
-
absoluter blödsinn, das kenntnisse von foldr/l für viele sprachen völlig irrelevant!
Im grunde genommen sind die meisten Algorithmen von <algorithm> einfach nur eine Faltung.
-
Beta Beater schrieb:
Für ein Open Source Projekt will ich einen Standard für den Programmierstil entwerfen. Ich muss mich entscheiden, ob Funktionen rekursiv oder iterativ geschrieben werden.
Hängt das nicht ein klein wenig von der Aufgabe ab, die ein Algorithmus zu lösen hat?
Benötigt er eine konstante Zahl von Zwischenergebnissen (Fibonacci 2, Baumtraversierung... je nach Baumgröße). Wenn man nicht weiß, wieviele Zwischenergebnisse man benötigt, ist ein Stack hilfreich, den man in stackbasierten Programmiersprachen hat, indem man eben rekursiv arbeitet.
Braucht man keinen Stack, bedeutet Rekursion unnötige Kosten. Braucht man einen Stack, ist der Funktionsstack eigentlich zu groß (also weiterhin unnötige Kosten), aber praktischerweise leicht verfügbar und bei einer Baumtraversierung sind rekursive Aufrufe (Kind->"und dort tue das gleiche wie hier") auch semantisch logisch.
Und so würde ich nicht festlegen wollen, ob man Funktionen grundsätzlich iterativ oder rekursiv geschrieben werden müssen.
-
Gregor schrieb:
Beta Beater schrieb:
Ich muss mich entscheiden, ob Funktionen rekursiv oder iterativ geschrieben werden.
Ich denke nicht, dass man das vorschreiben sollte. Was übersichtlicher oder sinnvoller ist, hängt vom Einzelfall ab.
(...)+1
Xin schrieb:
Beta Beater schrieb:
Für ein Open Source Projekt will ich einen Standard für den Programmierstil entwerfen. Ich muss mich entscheiden, ob Funktionen rekursiv oder iterativ geschrieben werden.
Hängt das nicht ein klein wenig von der Aufgabe ab, die ein Algorithmus zu lösen hat?
+1
-----------------
@Beta Beater
Die Frage hat sich so für mich noch nie gestellt. Gewisse Dinge sind rekursiv einfacher, die schreib' ich dann auch automatisch rekursiv, andere sind iterativ einfacher, die schreib' ich dann iterativ."Interessant" (bzw. lästig) wird es für mich erst dann, wenn ich genau das andere implementieren muss.
Also z.B. iterativ statt rekursiv weil rekursiv den Stack sprengen könnte. Oder rekursiv statt iterativ weil ich mit einer Sprache arbeiten muss die keinen Mutable State erlaubt (bzw. an der Stelle nicht erlaubt, wie z.B. C++ beiconstexprFunktionen).
