Rekursion vs. Iteration

[MaBuSE]

Zitat von angos:

da ich die Iteration meist als den lesbareren Quellcode ansehe nutze ich nur in Ausnahmefällen eine Rekursion.

Das ist erstaunlich, da bei komplexen Problemen der Rekursive Ansatz meist besser lesbar ist.

z.B. QuickSort

[Mithrandir]

Zitat von MaBuSE:

besser lesbar ist.

Besser lesbar = Besser verständlich

Ich habe nämlich teilweise erhebliche Probleme bei rekursiven Funktionen zu erkennen, was sie genau macht. Mag aber auch an der fehlenden Übung liegen, weil ich der Rekursion eigentlich immer aus dem Weg gegangen bin.

(In der Hochsprachenprogrammierungs - Prüfung war das dann leider nicht mehr möglich... )

[himitsu]

Es kommt vielleicht auf die Daten an?

Bei der Abarbeitung von Baumstrukturen (z.B. Dateien/Verzeichnisen) empfinge ich rekursiv übersichtlicher/verständlicher.

Bei QuickSort komm ich interativ auch besser zurecht, aber dort wird ja eine lineare Datenstruktur stückchenweise abgearbeitet.

[Webo]

Zitat von MaBuSE:

Hallo,
mich würde mal interessieren, ob Ihr in Euren Programmen ehr zur Rekursion oder zur Iteration neigt.

Ich nutze hauptsächlich die Interation - zum Einen weil ich es so gelernt habe und zum Anderen weil es meiner Ansicht nach besser "lesbar" ist.

[SirThornberry]

In deinem einfachen Beispiel würde ich ganz klar die iterative Variante verwenden.
Wenn es aber darum geht zum Beispiel Verzeichnisse und deren Unterverzeichnisse zu durchsuchen wo das aktuelle Verzeichnis für die spätere Weitersuche festgehalten werden muss, verwende ich ganz klar die rekursive Variante.

ich kann für mich also sagen:
- iterativ wenn nichts pro Schritt gemerkt werden muss
- rekursive wenn pro Schritt sich etwas gemerkt werden muss

Ich bevorzuge es also mir keinen eigenen Stack in Form einer Variablen basteln zu müssen sondern greife dann auf den tatsächlichen Stack zurück.

[idefix2]

Es kommt wohl auf die Problemstellung an. Oft ist der iterative Ansatz nicht mit nennenswertem Mehraufwand verbunden, dann zahlt sich eine rekursive Konstruktion nicht aus. Beispielsweise würde ich es als Unfug bezeichnen, in einem "echten" Programm n! rekursiv zu berechnen (das ist nicht als Kritik am obigen Beispiel zu verstehen, weil zur Illustration der Rekursion eignet sich das Beispiel natürlich hervorragend) .

Es gibt aber durchaus Situationen (Quicksort wurde als Beispiel genannt), in denen sich ein Algorithmus rekursiv wesentlich klarer und einfacher darstellen lässt, als durch eine "künstliche" Auflösung der Rekursion zu einem iterativen Verfahren. In so einem Fall würde ich unbedingt den rekursiven Ansatz verwenden, auch um den Preis von ein paar zusätzlichen Bytes Stackverbrauch.

Etwas weiter oben ist das Stichwort "Tail Call Recursion" gefallen. Wenn es sich nur um eine solche handelt (rekursiver Aufruf nur einmal am Ende der rekursiven Prozedur), ist die Iteration wohl vorzuziehen - Die Berechnung von n! ist so ein Beispiel.

[Corpsman]

Guten Morgen,

Ich nutze Rekursion wie Iteration. die Wahl der Technik legt das zu lösende Problem fest. Wenn ich die Wahl habe nehme ich in der Regel die Iteration, oder Baue die Rekursion mittels einer "FILO" nach, zwecks sparen der rekursiven Aufrufe.

Bei sehr einfachen Rekursionen ist es wie idefix2 ja schon schrieb, eh so, dass der Compiler die Rekursion weg optimiert.

Ich Denke im Zweifel sollte man sich immer für die Lesbarkeit entscheiden. Und erst nach gründlicher Prüfung auf einen "optimierteren" Code umsteigen, die Frage die sich hier immer stellt : Rechtfertigt der Nutzen den Mehraufwand. In einem einfachen Programm wie n! sicher nicht. Bei den Fibonacci Zahlen hingegen ist die Iterative Lösung auf jeden Fall vor zu ziehen.

[idefix2]

Zitat:

Bei sehr einfachen Rekursionen ist es wie idefix2 ja schon schrieb, eh so, dass der Compiler die Rekursion weg optimiert.

Macht das der Compiler wirklich? Ich habe eigentlich geschrieben, dass ich in so einem Fall die Iteration verwenden würde, das heisst, dass ich quasi die Rekursion selbst manuell wegoptimieren würde.

[mkinzler]

Es ist aber auch eine Geschmacksache.

[QuickAndDirty]

Und ich hasse Rekursion...vor allem beim debuggen...es ist die Hölle
besonders scheiße finde ich unabsichtliche Rekursion...wo man eine Methode aufruft die über zig andere Methoden wieder sich selbst aufruft...

Lustig zu debuggen.


Es gab mal irgend eine Formel wie man ein Rekursives Problem umstellen kann so das es Iterativ abgebildet wird...habe das irgendwann man an der uni gelernt...aber wieder vergessen