Sind rekursive Funktionen übersichtlicher?

Hi.

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.

Stimmt es, dass einige Leute das Rekursive übersichtlicher finden?

Wenn es wirklich übersichtlicher ist, werde ich es wohl wählen. Die Performance ist für mich momentan Nebensache. Wichtiger ist für mich, dass die Programmierer sich gut im Code zurecht finden. Zumal es auch keine hohe Performance benötigt.

MfG

CJosef

Hi,
das sollte keine Frage der Übersicht sein. Rekursive Funktionen können mal eben schnell den Stack sprengen und dann läuft erstmal garnix mehr.

knivil

Stimmt es, dass einige Leute das Rekursive übersichtlicher finden?

Ja, ich finde meine rekursiven Funktionen gegenueber meinen iterativen varianten uebersichtlicher. Aber in beiden Faellen kann trotzdem Spagetticode entstehen.

Ich muss mich entscheiden, ob Funktionen rekursiv oder iterativ geschrieben werden.

Also du willst pauschal dem Programmierer vorschreiben, ob er etwas rekursiv bzw. iterativ implementiert. Diese Vorschrift wuerde ich einfach ignorieren.

Rekursive Funktionen können mal eben schnell den Stack sprengen und dann läuft erstmal garnix mehr.

Wenn man nicht weiss, was man tut, dann hilft sowieso keine Vorschrift. Meine rekursiven Funktionen sprengen keinen Stack.

Gregor

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. Es gibt durchaus Fälle, in denen es intuitiver ist, eine Funktion rekursiv zu schreiben. Guck Dir mal das Standardbeispiel an, das man bei rekursiven Funktionen immer hat: Eine Funktion, die Fibonaccizahlen ausrechnet. Die sind mathematisch rekursiv definiert und entsprechend sieht eine rekursive Lösung hier sehr elegant aus. ...andererseits: wenn man nicht aufpasst, hat sie eine deutlich schlechtere Komplexität (ein schlechteres Laufzeitverhalten) als eine iterative Lösung. Aber so etwas unterscheidet sich von Fall zu Fall.

Ich denke, dass Du hier dem jeweiligen Programmierer die Freiheit lassen solltest, das selbst zu entscheiden. Diese Frage hängt sehr von der Sichtweise des jeweiligen Programmierers ab. Ich denke nicht, dass es sinnvoll ist, wenn der Programmierer zu einer rekursiven Lösung gezwungen wird, wenn er eigentlich eine iterative im Kopf hat.

Cyres

CJosef schrieb:

Hi,
das sollte keine Frage der Übersicht sein. Rekursive Funktionen können mal eben schnell den Stack sprengen und dann läuft erstmal garnix mehr.

Wenn man einfach drauf los programmiert kann das sehr schnell passieren, aber nicht, wenn man Ahnung von theoretischer Informatik hat. Man sollte bei Rekursion wenn möglich das Bellman-Optimalitätsprinzip in der dynamischen Programmierung beachten.

knivil

Wenn ich beispielsweise ein fold_left / fold_right schreibe, denke ich nicht an dynamische Programmierung oder das Bellman-Optimalitätsprinzip. Es wird auch kaum in Einsteigerliteratur fuer beispielsweise funktionale Programmierung erwaehnt. Meist geht es um endrekursiv ja/nein.

Cyres

knivil schrieb:

Wenn ich beispielsweise ein fold_left / fold_right schreibe, denke ich nicht an dynamische Programmierung oder das Bellman-Optimalitätsprinzip. Es wird auch kaum in keiner Einsteigerliteratur fuer beispielsweise funktionale Programmierung erwaehnt. Meist geht es um endrekursiv ja/nein.

Das man es nicht immer Anwenden kann/muss ist mir wohl bewusst. 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

Was ich damit sagen möchte: Es gibt gute und schlechte Möglichkeiten rekursiv zu Programmieren. Im Gegensatz zur prozeduralen progammierung (in diesem Fall meistens mit Stacks) spielt der Speicherverbrauch nicht so eine große Rolle wie bei der funktionalen Programmierung.
Andere Beispiele wäre

Single/All-Pairs-Shortest-Path-Problem (z.B. Bellman-Ford, Dijkstra oder Floyd-Warschall)
Rucksackproblem (oder andere NP-Harte Algorithmen)
Counting-Sort (oder viele andere Sortier-/Suchalgorithmen)

rüdiger

CJosef schrieb:

Hi,
das sollte keine Frage der Übersicht sein. Rekursive Funktionen können mal eben schnell den Stack sprengen und dann läuft erstmal garnix mehr.

Das ist der Grund, warum Rekursion in C oder C++ oft verboten wird, wenn es um kritische Software geht. Es gibt keinen Weg herauszufinden, ob der Stack noch groß genug ist und es gibt erst recht keinen Weg nach einem Stackoverflow sinnvoll weiterzumachen. Aber wenn die Software nicht so kritisch ist, dann würde ich das einfach nicht vorschreiben. Wie Gregor bereits gesagt hat, sehen viele Algorithmen rekursiv halt doch simpler aus. In anderen Fällen kann die rekursive Lösung aber deutlich komplizierter aussehen.

knivil

Es gibt gute und schlechte Möglichkeiten rekursiv zu Programmieren.

Es gibt gute und schlechte Möglichkeiten prozedural zu programmieren. ...

Was ich damit sagen möchte:

Ist mir immernoch unklar.

Meine pauschale Aussage: Rekursive Algorithmen bieten sich immer dort an, wo rekursive Datenstrukturen benutzt werden. Das sind aber nicht die einzigen Moeglichkeiten, beispielsweise LU-Zerlegung einer Matrix. Muss man nicht, kann man aber.

Jester

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?

knivil

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_right oder andere Rekursionschema. Ersteres ist schwerer als letzteres.

Cyres

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!

Cyres

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...

knivil

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.

Xin

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.

hustbaer

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++ bei constexpr Funktionen).