Rekursion vs. Iteration

[Delphi-Laie]

Zitat von negaH:

Ich meine das sollte vom verwendeten Algorithmus und damit Zielsetzung abhängig gemacht werden. Es gibt nur sehr wenige und schwache Begründungen warum man zB. einen mathematischen Algorithmus, der per Formel rekursiv formuliert wurde, in Software später iterativ zu implementieren.

Speicherverbrauch und Geschwindigkeit sind schwach?

Dann müßte die Assemblerprogrammierung erst recht ohne Existenzberechtigung dastehen!

Zitat von negaH:

Erstens dient ja die Formel als Basis und wenn man 1 zu 1 diese als Implementierung in SW wieder findet so erhöht das enorm die Verständlichkeit. Zweitens sind rekursive Formeln/Algos meistens einfacher verständlich.

Naja, auf Anhieb habe ich nur die Fakultät und die Fiboncci-Folge als Paradebeispiele. Sicher erklärt die (nichtiterative) Formel bei letzterem nicht das Wesen jener Folge, aber sie ist als solche deshalb nicht weniger verständlich.

Zitat von negaH:

Die Hauptvorteile einer iterativen Variante, wie Geschwindigkeit, Speicherverbrauch sind in meinen Augen heutzutage absolut vernachlässigenbar.

Jedes (!) Windows beweist den Gegensatz: Windows macht nämlich praktisch jeden Computer sofort, früher oder später zur Schnecke. Manchmal habe ich sogar den Verdacht, daß absichtlich Bremsschleifen dorthinein implementiert wurden.

Zitat von negaH:

In meiner langjährigen Praxis haben sich bei vielen Implementierungen diese "Vorteile" als wirklich nur mariginal herausgestellt. Wichtiger war es dann immer den benutzen Algorithmus zu optimieren oder einen besseren zu benutzen.

Zu optimieren in welcher Hinsicht? Geschwindigkeit? Speicherverbrauch? Die wurden doch weiter oben schon als relativ unwichtig gebrandmarkt.

Zitat von negaH:

PS: Gegenteilig betrachtet gibt es rekursiv formulierte Probleme die als iterative Variante wirklich sehr sehr schwer zu verstehen sind (und ich habe solche iterativen Monster schon öfters analysiert

Könntest Du bitte Beispiele nennen?

[mkinzler]

Zitat von MrSpock:

Natürlich kommt es auf das Problem an, aber ich liebe Rekursionen.

Ich auch

Zitat von Delphi-Laie:

Speicherverbrauch und Geschwindigkeit sind schwach?

Das sollte bei Fehlerfreienarmen Code kein Problem sein

[idefix2]

Zitat:

Dann müßte die Assemblerprogrammierung erst recht ohne Existenzberechtigung dastehen!

Viel wird ja heute wirklich nicht mehr in Assembler programmiert - Sinnvoll ist das wirklich nur mehr bei sehr wenig oft durchlaufenem extrem zeitkritischem Code. Ungeschickte Umsetzung des Algorithmus ist meistens eine wesentlich schlimmere Tempobremse als die im Vergleich zu Assembler geringere Effizienz des Compiler-generierten Codes. Und auch der Overhead, der durch Rekursionen entsteht, ist meistens vernachlässigbar - zugegebenermassen nicht immer, im Beispiel Fibonaccizahlen wäre eben eine "beinhart durchgezogene Rekursion" ein krasses Beispiel von ungeaschickter Umsetzung.

Wichtig ist in meinen Augen, dass Code möglichst leicht verständlich ist. Wenn eine Vorgangsweise sich rekursiv leichter beschreiben lässt als iterativ, dann wird auch das rekursive Perogramm leichter verständlich sein als eine Variante, in der die Rekusion manuell mit einer Reihe von zusätzlichen Schritten, wie einer manuellen Stackverwaltung, zu einem iterativen Verfahren aufgelöst wird. Aber die Erkärung "Multipliziere alle Zahlen von 1 bis n miteinander" ist leichter und unmittelbarer verständlich als "Für die Zahl x=1 ist das Ergebnis =1, Für x>1 nimm den Funktionswert f(x-1) und multipliziere den mit x", deshalb ist in dem Fall der iterative Ansatz vorzuziehen.

Ich sehe das ähnlich wie beim goto-Statement. Prinzipiell sollte man goto vermeiden, und zwar deshalb (und NUR deshalb), weil ein Label beim Studium eines Programms und bei der Fehlersuche zusätzliche Aufmerksamkeit erfordert (Woher wird der Label angesprungen, gibt es vielleicht noch andere Stellen im Programm, die zu diesem Label verzweigen, auf welche Invarianten kann ich mich verlassen, wenn der Code, der auf den Label folgt, durchlaufen wird, etc.). Andererseits, wenn ich eine mehrfach geschachtelte Schleife verlassen will, ist mir ein Label hinter der Schleife immer noch viel lieber als eine Krampflösung mit drei booleans und 4 zusätzlichen Abfragen - das kostet nämlich noch viel mehr Aufmerksamkeit als die Verwendung eines Labels, und darum geht es doch nach vor allem.

Natürlich gibt es Sonderfälle. Die eben angeführte Fibonaccizahl ist ein solcher, bei Problemen im wirklichen Leben ist so etwas eher selten. Es ist dieses Beispiel aber auch ähnlich einer Tail call Rekursion, wenn auch mit zwei rekursiven Aufrufen, weshalb sich hier der iterative Ansatz von vorneherein anbietet. Selbstverständlich wird man immer, wenn Teilergebnisse wiederholt benötigt werden, diese puffern, dann ist der rekursive Algorithmus wahrscheinlich nicht viel langsamer als der iterative (würde aber in diesem Sonderfall wirklich ordentlich mehr Speicher fressen, weil beim iterativen Ansatz immer nur die letzten beiden berechneten Werte gespeichert werden müssten.

[Delphi-Laie]

Also, die Optimierung des Algorithmus' (möglich in mehrerlei Hinsicht) als eine Zielfunktion darf man hier demnach als unstrittig konstatieren.

Auch wenn die Rekursion vielleicht sogar in den meisten Fällen eine kurze und elegante Problem(lösungs)beschreibung liefert, so kann dennoch die Algorithmenoptimierung durchaus in einer Beseitigung der Rekursion zu suchen bzw. zu finden sein.

Es mag Fälle geben, in denen es ohne Rekursion nicht geht (Ackermann-Funktion, für Bäume und andere hierarchische Datenstrukturen, Quicksort), doch in allen Fällen, in denen beide Varianten möglich sind, sollte man Iteration und Rekursion möglichst unvoreingenommen gegenüberstellen und die Vor- und Nachteile abwägen.

Insofern sind einseitige, ja fast schon ideologisch motivierte Sympathiebekundungen, so befangen letztlich jeder auch im innersten ist, hier eher fehl am Platze.

[negaH]

Zitat:

Ein weiterer Vorteil von rekursiven Implementierungen ist die Korrektheit.

Korrekt. Man wird dann nämlich sehr oft den Beweis für die Korrektheit ebenfalls rekursiv formulieren können und das ist wesentlich einfacher. Um Fehldeutungen dieses Satzes von vornherein auszuschließen. Ich beziehe mich auf den Beweis der Korrektheit des angewendeten Algorithmus auf höherer Ebene. Also nicht ob das Program am Ende tut was man geplant hat, also den Einzelfall sondern den Beweis das das Program in jedem Falle das tuen wird was man geplant hat. Sowas erschlägt man nicht indem man ein Testprogram schreibt und einige Tests laufen lässt sondern sowas muß beweisbar sein, auch auf dem Papier als Formel, also formale Korrektheit.

Gruß Hagen

[negaH]

Zitat:

Auch wenn die Rekursion vielleicht sogar in den meisten Fällen eine kurze und elegante Problem(lösungs)beschreibung liefert, so kann dennoch die Algorithmenoptimierung durchaus in einer Beseitigung der Rekursion zu suchen bzw. zu finden sein.

Ja, aber von der Priorität her erst als allerletztes Mittel (Ausnahmen bestätigen die Regel).
Und wie ich vorherig schon beschrieb gibt es nicht nur die schmale Sichtweise auf die ASICs, sondern die Frage "iterativ vs. rekursiv" lässt sich für jede Hardware stellen, zb. auch auf Papier, FPGAs uvm.

Gruß Hagen

[jfheins]

Also was Geschwindigkeitsoptimiereung angeht halte ich mich an diese Rangliste:
(absteigend nach Wichtigkeit)
1. verwendeter Algorithmus
2. Art der Implementierung
3. Programmierspache

=> Wenn man den richtigen Algorithmus wählt, ist die Frage rekursiv/iterativ untergeordnet, solange man es vernüftig macht.

[negaH]

Zitat:

=> Wenn man den richtigen Algorithmus wählt, ist die Frage rekursiv/iterativ untergeordnet...

Aus Sicht der Performance-/Speicherunterschiede. Aber meiner Meinung nach eben nicht aus Sicht der Verständlichkeit und Wartbarkeit.

Gruß Hagen

[gammatester]

Zitat von jfheins:

Wenn man den richtigen Algorithmus wählt, ist die Frage rekursiv/iterativ untergeordnet, solange man es vernüftig macht.

Das ist mM eine leere Ausssage, denn der Algorithmus enthält eine Beschreibung der Lösungsschritte und da steht natürlich drin, ob das ganze rekursiv oder iterativ ist. Wenn dem nicht so wäre, hättest Du eine unvollständige Beschreibung mithin gar keinen keinen Algorithmus.

[Delphi-Laie]

Zitat von jfheins:

=> Wenn man den richtigen Algorithmus wählt, ist die Frage rekursiv/iterativ untergeordnet, solange man es vernüftig macht.

Die Wahl des „richtigen“ (was ist damit konkret gemeint?) Algorithmus besteht doch oft genug in der Entscheidung, ob rekursiv oder iterativ.

Ich schlage mal folgendes vor: Vergleiche mal die Berechnung der Koeffizienten eines charakteristischen Polynoms einer quadratischen Matrix mit Rekursion (nach der Determinantenberechnung nach dem Laplaceschen Entwicklungssatz) mit ihren iterativen Pendants (der schnellste mir bekannte ist der von Le Verrier). Die Komplexität unterscheidet sich zwischen beiden um astronomischen Größenordnungen!

All' die, dier hier der Rekursion das Wort reden, konnte ich, sofern beide Alternativen (als Rekursion und Iteration oder sogar simpleres) zur Lösung eines Problemes verfügbar sind, noch keine einzigen Fall nennen hören, bei dem die Rekursion hinsichtlich Komplexität die überlegene Lösung darstellt. Ich bin gespannt darauf.