Rekursion vs. Iteration

[MaBuSE]

Hallo,
mich würde mal interessieren, ob Ihr in Euren Programmen ehr zur Rekursion oder zur Iteration neigt.
Es können ja schließlich alle Rekursionen durch Interationen ersetzt werden.

• Rekursion
  • Vorteile:
    • meist kurz (wenig Quellcode)
    • oft verständlicher als Iteration
  • Nachteile:
    • meist langsamer als Iteration in der Ausführung
    • es wird von Anfängern gern mal die Abbruchbedingung vergessen
• Iteration
  • Vorteile:
    • meist schneller als Rekursion in der Ausführung
  • Nachteile:
    • meist längerer Quellcode
    • oft weniger verständlich als Resursion

Für alle die mit dem Begriff Rekursion und Iteration nciht vertraut sind:

• Iteration
  http://de.wikipedia.org/wiki/Iterative_Programmierung
  
• Rekursion
  http://de.wikipedia.org/wiki/Rekursive_Programmierung

Beispiel:
Neue Anwendung -> Form1, ein TButton -> Button1 und ein TMemo -> Memo1
Methode rec ist recursiv (ruf sich also selbst wieder auf)
methode iter ist iterativ (in diesem Fall eine einfache For Schleife)

Delphi-Quellcode:

...
procedure TForm1.Button1Click(Sender: TObject);
var
  i: Integer;
begin
  Memo1.Lines.Clear;
  Memo1.Lines.Add('i   rec(i)   iter(i) ');
  Memo1.Lines.Add('--- -------- --------');
  for i := 0 to 10 do
  begin
    Memo1.Lines.Add(Format('%2d: %8d %8d', [i, rec(i), iter(i)]));
  end;
end;

function TForm1.iter(i: Integer): integer;
var
  j: Integer;
begin
  Result := 1;
  for j := 1 to i do
  begin
    Result := Result * j;
  end;
end;

function TForm1.rec(i: Integer): integer;
begin
  if i = 0 then Result := 1
           else Result := i * rec(i-1);
end;
...

Das Ergebnis:

Code:

i   rec(i)   iter(i) 
--- -------- --------
 0:        1        1
 1:        1        1
 2:        2        2
 3:        6        6
 4:       24       24
 5:      120      120
 6:      720      720
 7:     5040     5040
 8:    40320    40320
 9:   362880   362880
10:  3628800  3628800

Viele Grüße
MaBuSE

ps:Ich wollte schon immer mal als Erster in einem Forum schreiben :love: :dp: :love:

[freak4fun]

Meistens Iteration, weil es leichter zu verstehen ist. ;)

[nahpets]

Hallo,

Zitat:

Zitat von MaBuSE

Es können ja schließlich alle Rekursionen durch Interationen ersetzt werden.

Stimmt das?

Wie kann ich die Suche z. B. im Verzeichnisbaum durch eine Iteration abbilden?

Zur eigentlichen Frage:

Kommt drauf an, was leichter und verständlicher zu implementieren ist, wobei ich nur selten auf Aufgabenstellungen stoße, die rekursive lösbar sind. Das Meiste ist das Sammeln von Datenbankdaten und deren Ausgabe.

[Khabarakh]

Zitat:

Zitat von nahpets (Beitrag 1026800)

Stimmt das?

Wie kann ich die Suche z. B. im Verzeichnisbaum durch eine Iteration abbilden?

Ja, Rekursion lässt sich immer als Iteration + Stack umsetzen. Nicht zufällig heißt das Ding, auf dem die Variablen landen, gleich ;) .

In deinem Beispiel: Das Ursprungsverzeichnis auf einen Stack werfen, solange dieser nicht leer ist, das oberste Element behandeln und alle Unterverzeichnisse hinzufügen.

Rekursionen sind wirklich wunderhübsch, aber da die wenigsten imperativen Sprachen Tail Call Optimization kennen, gibt es nur wenige Probleme (z.B. Quicksort), bei denen man keinen Stacküberlauf riskiert.

[himitsu]

Die Interative Lösung hat noch andere Vorteile
(gut, der Nachteil, daß Interativ meißt schieriger/umständlicher/unverständlicher zu implementieren ist, sei mal dahingestellt)

Vorteil, da man den Stack selber verwaltet, kann man auch mal ganz leicht aus der Funktion rausspringen und diese später erneut an selber Stelle weiter abarbeiten.

Im Fall von FindAllFiles wäre z.B. sowas möglich:

Delphi-Quellcode:

Suche := TSucheAlleDateien.Create('c:\', '*.*');
while Suche.NochWasDaFragezeichen and not SollAbgebrochenWerdenFragezeichen do
  WriteLn(Find.WasDennFragezeichen);
Suche.Free;

Wobei man hier die nächste Datei erst in NochWasDaFragezeichen suchen könnte.

PS: http://www.delphipraxis.net/142669-f...iterative.html

[Luckie]

Der Speicherverbrauch.

[s.h.a.r.k]

Es kommt vor allem auf die Datenstruktur drauf an, und wenn sich anbietet eine Rekursion zu nehmen, dann nutze ich diese auch. Aber egal ob Rekursion oder Iteration, es muss schon auch dokumentiert werden, was gemacht wird ;)

[himitsu]

Zitat:

Zitat von Luckie (Beitrag 1026842)

Der Speicherverbrauch.

Ohne unnütze Stackframes sollte man bei Beiden doch etwa auf's Selbe rauskommen?

[Delphi-Laie]

Über dieses Thema der - vermutlich - theoretischen Informatik gelangten bestimmt schon manche an ihren Doktorhut.

Tendenziell ist die Iteration schneller und von geringerem Speicherbedarf (s. Luckies Bemerkung), vor allem ohne Stackspeicherverbrauch. Mit Rekursion ist so manche Problemlösung dafür schneller und kürzer beschrieben - wenigstens auf dem Papier. Zudem kann ich mir vorstellen, daß die Rekursion als etwas anspruchsvoller, also akademisch eleganter empfunden wird.

Ursache beider sind Ähnlichkeiten und Wiederholungen im Programmablauf, und deren Vorwegnahme im Programmcode (in gewisser Weise ist ein Programm ein Ablaufplan für ein später laufendes Programm, besser, für die Menge seiner potentiell ablaufenden Programme) kann eben auf unterschiedliche Weise beschrieben werden.

Zitat:

Zitat von Khabarakh (Beitrag 1026815)

Zitat:

Zitat von nahpets (Beitrag 1026800)

Stimmt das?

Wie kann ich die Suche z. B. im Verzeichnisbaum durch eine Iteration abbilden?

Ja, Rekursion lässt sich immer als Iteration + Stack umsetzen. Nicht zufällig heißt das Ding, auf dem die Variablen landen, gleich ;) .

Ist damit so eine Art „Pseudo-Entrekursionierung/-rekursivierung“ gemeint? So etwas lernte ich in Robert Sedgewicks Standardwälzer beim Quicksort kennen und implementierte es auch in mein Sortierkino. Im Prinzip wird die Stackbehandlung „zu Fuß“ nachgebildet. Grund ist, daß Quicksort einer der Algorithmen ist, die sich nicht (wenistens nicht zufriedenstellend) derekursionieren/-rekursivieren lassen. Auch bei hierarchischen bzw. Baumstrukturen mit beliebiger bzw. unbekannter Tiefe ist mir ein nichtrekursives, also iteratives Vorgehen nicht simpel einleuchtend (mag sein, daß es möglich ist). Allerdings gehöre ich zu dem - wohl übergroßen - Anteil der Forumsmitglieder, die nicht Informatik studierten.

Edit: Das neue Timeout ist eine Zumutung, Daniel, bitte tue etwas dagegen!

[angos]

Zitat:

Zitat von MaBuSE (Beitrag 1026779)

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

Hi,

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

Gruß
Ansgar

[MaBuSE]

Zitat:

Zitat von angos (Beitrag 1026865)

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:

Zitat von MaBuSE (Beitrag 1026895)

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:

Zitat von MaBuSE (Beitrag 1026779)

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 :wall:

[Corpsman]

Zitat:

Zitat von idefix2 (Beitrag 1027700)

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.

In meiner Compilerbau Vorlesung haben wir das zumindest durch genommen,d.h. theoretisch geht es. Ob es der Delphi Compiler allerdings macht, dass ist natürlich ungewiss. In den entsprechenden Manuals müsste dass aber stehen.

Zitat:

Zitat von QuickAndDirty (Beitrag 1027707)

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 :wall:

Das war das Umformen mittels FILO ;). Ich kanns zwar implementieren, wie es genau heist weis ich auch nicht *g*

[p80286]

Iteration / Rekursion ist wie
Wanderschuhe / Pumps.
Das eine praktisch (auch für geistige Dünnbrettbohrer wie mich zuverstehen), das andere knackig, elegant und nicht zu gebrauchen (auf das "einfache" Debugging wurde ja schon mehrfach hingewiesen).

Das mit dem Stacküberlauf ist mir allerdings seit seligen TP-Zeiten nicht mehr passiert.


Gruß
K-H

[MrSpock]

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

Sie sind elegant, kurz und m.E. leicht zu verstehen. Zugegeben: das sage ich jetzt. Ich kann mich noch gut an meine erste "Programmieren" Klausur an der Uni erinnern. Dort ging es darum ein Problem mittels Rekursion zu lösen. Das Programm war auf Papier niederzuschreiben (also nix mit mal schnell am PC testen). Es waren 12 Zeilen Code, die mich 45 Minuten Zeit gekostet haben. Heute schreibe ich Rekursionen in der Regel gleich hin (meistens sogar richtig :zwinker: ).

[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. 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. Die Hauptvorteile einer iterativen Variante, wie Geschwindigkeit, Speicherverbrauch sind in meinen Augen heutzutage absolut vernachlässigenbar. 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.

Meiner Meinung nach ist es also wenig sinnvoll die Kriterien Performance und Speicherverbrauch in den Vordergrund zu stellen. Wichtiger ist Verständlichkeit, Wartbarkeit und Flexibilität.

Gruß Hagen

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

[Delphi-Laie]

Zitat:

Zitat von negaH (Beitrag 1027836)

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:

Zitat von negaH (Beitrag 1027836)

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:

Zitat von negaH (Beitrag 1027836)

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:

Zitat von negaH (Beitrag 1027836)

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:

Zitat von negaH (Beitrag 1027836)

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:

Zitat von MrSpock

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

Ich auch

Zitat:

Zitat von Delphi-Laie

Speicherverbrauch und Geschwindigkeit sind schwach?

Das sollte bei Fehlerfreienarmen Code kein Problem sein

[gammatester]

Zitat:

Zitat von negaH (Beitrag 1027836)

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.

Meiner Meinung nach ist es also wenig sinnvoll die Kriterien Performance und Speicherverbrauch in den Vordergrund zu stellen. Wichtiger ist Verständlichkeit, Wartbarkeit und Flexibilität.

Naja, ganz so einfach ist es ja auch nicht. Wenn man als (zweites Standardbeispiel neben Fakultät) die Fibonacci-Zahlen gemäß der rekursiven Definition fib(n) = fib(n-1)+fib(n-2) umsetzt:

Delphi-Quellcode:

function fib(n: int64): int64;
begin
  if n=0 then fib := 0
  else if n=1 then fib := 1
  else fib := fib(n-1)+fib(n-2);
end;

wird man für fib(90) viel Geduld brauchen. Die iterative Lösung ist für int64 praktisch instantan. Das es für sehr große Zahlen einen noch viel besseren Algo gibt, wissen einige. Die rekursive Variante ist jedoch bezüglich "Einfachheit, Verständlichkeit, Wartbarkeit und Flexibilität" nicht zu toppen, ist aber praktisch unbrauchbar.

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

[JasonDX]

Seit meinem (unfreiwilligen) Zusammenstoß mit funktionalen Programmiersprachen im letzten Semester implementiere ich mehr und mehr rekursiv. Es ist einfach schöner und eleganter; Nur noch selten implementiere ich einen Algorithmus, den ich erst auf Papier erarbeitet habe, iterativ.

Zitat:

Zitat von Delphi-Laie (Beitrag 1027841)

Zitat:

Zitat von negaH (Beitrag 1027836)

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!

Tut es (fast) auch. Einzige Existenzberechtigung ist das minimum an dazwischenliegenden Schichten zwischen Code&Hardware.

Zitat:

Zitat von Delphi-Laie (Beitrag 1027841)

Zitat:

Zitat von negaH (Beitrag 1027836)

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.

In deinem letzten Satz sollte dir der Widerspruch deiner Aussage auffallen. "Man versteht nicht das Wesen der Folge, aber der Code ist nicht weniger verständlich". Der Code ist vllt. nicht weniger lesbar, aber seine Aufgabe ist deutlich unverständlicher.

Zitat:

Zitat von Delphi-Laie (Beitrag 1027841)

Zitat:

Zitat von negaH (Beitrag 1027836)

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.

Optimierung auf Laufzeitkomplexität. (Nein, nicht das selbe wie Geschwindigkeit).

Zitat:

Zitat von Delphi-Laie (Beitrag 1027841)

Zitat:

Zitat von negaH (Beitrag 1027836)

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?

Alles, auf was sich eine Baumtraversierung zurückführen lässt - und das ist ziemlich viel.

Ein weiterer Vorteil von rekursiven Implementierungen ist die Korrektheit. Im Theoretischen Bereich wird alles was geht rekursiv beschrieben. Es vereinfacht die Validierung des Algorithmus um Welten (Schonmal versucht zu beweisen, dass deine Schleife wirklich die Fibonacci-Reihe berechnet? ^^). Eine rekursive Beschreibung rekursiv implementieren bringt dann deutlich weniger Probleme und Fehlerpotential mit sich, als den rekursiv beschriebenen Algorithmus iterativ zu implementieren.

greetz
Mike

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

[Delphi-Laie]

Zitat:

Zitat von JasonDX (Beitrag 1027935)

Zitat:

Zitat von Delphi-Laie (Beitrag 1027841)

Zitat:

Zitat von negaH (Beitrag 1027836)

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.

In deinem letzten Satz sollte dir der Widerspruch deiner Aussage auffallen. "Man versteht nicht das Wesen der Folge, aber der Code ist nicht weniger verständlich". Der Code ist vllt. nicht weniger lesbar, aber seine Aufgabe ist deutlich unverständlicher.

Wo ist ein/der Widerspruch?

Ohne Rekursion - sogar ohne Iteration - kann man die Glieder der Fibonacci-Folge über Berechnungen mit der (Quadrat-)Wurzel aus 5 ermitteln. Diese Formel ist leicht zu implementieren bzw. aus dem Quellcode (nur wenige Anweisungen, deshalb leicht zu erfassen) leicht die Formel abzuleiten. Doch wie man aus dieser Gleichung die rekursive Berechnung der Fibonaccifolgenglieder ermitteln soll, erschließt sich mir nicht, und ob es überhaupt möglich ist, können nur Mathematiker beantworten.

[MrSpock]

Ich denke, dass auch die meisten backtracking Probleme am besten über Rekursion gelöst werden.

z.B.: Damenproblem, Springerproblem, Wegesuche im Labyrinth

[gammatester]

Zitat:

Zitat von JasonDX (Beitrag 1027935)

(Schonmal versucht zu beweisen, dass deine Schleife wirklich die Fibonacci-Reihe berechnet? ^^). Eine rekursive Beschreibung rekursiv implementieren bringt dann deutlich weniger Probleme und Fehlerpotential mit sich, als den rekursiv beschriebenen Algorithmus iterativ zu implementieren.

Na Logo, und bei der Gelegenheit kommt man auch sofort auf den viel besseren Algorithmus: [F_{n+1}, F_n] = [[1 1], [1 0]] * [F_n, F_{n-1}]. Es läuft also darauf hinaus, die Potenzen der Matrix A = [[1 1], [1 0]] zu berechnen. Die einfache Iteration berechnet A^n via n-facher Multiplikation und ist O(n), der verbesserte Algo berechnen A^n nach dem binären "Quadriere-und-Multipliziere"-Algorithmus und ist O(log(n)).

[JasonDX]

Zitat:

Zitat von Delphi-Laie (Beitrag 1027946)

Zitat:

Zitat von JasonDX (Beitrag 1027935)

Zitat:

Zitat von Delphi-Laie (Beitrag 1027841)

Zitat:

Zitat von negaH (Beitrag 1027836)

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.

In deinem letzten Satz sollte dir der Widerspruch deiner Aussage auffallen. "Man versteht nicht das Wesen der Folge, aber der Code ist nicht weniger verständlich". Der Code ist vllt. nicht weniger lesbar, aber seine Aufgabe ist deutlich unverständlicher.

Wo ist ein/der Widerspruch?

Die rekursive Definition der Fibonacci-Folge ist trivial, und ihr Verlauf ist auf den ersten Blick halbwegs abschätzbar - im Gegensatz zur iterativen Implementierung; Dort ist eine Einschätzung der Funktion verhältnismäßig komplex.

Zitat:

Zitat von Delphi-Laie (Beitrag 1027946)

Ohne Rekursion - sogar ohne Iteration - kann man die Glieder der Fibonacci-Folge über Berechnungen mit der (Quadrat-)Wurzel aus 5 ermitteln. Diese Formel ist leicht zu implementieren bzw. aus dem Quellcode (nur wenige Anweisungen, deshalb leicht zu erfassen) leicht die Formel abzuleiten.

Ja, sie ist leicht implementierbar und hat (rein theoretisch) konstante Laufzeit - aber ein grobes Genauigkeitsproblem.

Zitat:

Zitat von gammatester (Beitrag 1027949)

Zitat:

Zitat von JasonDX (Beitrag 1027935)

(Schonmal versucht zu beweisen, dass deine Schleife wirklich die Fibonacci-Reihe berechnet? ^^). Eine rekursive Beschreibung rekursiv implementieren bringt dann deutlich weniger Probleme und Fehlerpotential mit sich, als den rekursiv beschriebenen Algorithmus iterativ zu implementieren.

Na Logo, und bei der Gelegenheit kommt man auch sofort auf den viel besseren Algorithmus: [F_{n+1}, F_n] = [[1 1], [1 0]] * [F_n, F_{n-1}]. Es läuft also darauf hinaus, die Potenzen der Matrix A = [[1 1], [1 0]] zu berechnen. Die einfache Iteration berechnet A^n via n-facher Multiplikation und ist O(n), der verbesserte Algo berechnen A^n nach dem binären "Quadriere-und-Multipliziere"-Algorithmus und ist O(log(n)).

Womit man dann zurück zum Punkt kommt, obs schöner/besser/toller/* ist den optimierten Algorithmus iterativ oder rekursiv zu implementieren ;)
Mein Beitrag war auf die iterative Schleife bezogen. Diese bringt keine Laufzeitverbesserung, ist dafür aber weniger intuitiv und damit schlechter erkennbar, von Fehlerquellen mal ganz abgesehn ;)

greetz
Mike

[negaH]

Die Eingangsfrage ist ob rekusive oder iterative Umsetzungen eines Algos besser oder schlechter ist.

Man kann nun Äpfel mit Birnen vergleichen oder unsachlich argumentieren (zb. was hat Assembler damit zu tuen, oder was hat die Implementierung von Windows damit zu tuen, oder welche Relevanz hat eine Diskussion wenn man zb. für Fibonacci einen komplett anderen Algorithmus als Lösung vorschlägt und das als Basis für eine Begründung wählt um die iterative Methode zu untermaueren ?)

Der einzige Grund warum eine rekursive Lösung unter Umständen einen leichten Performance-/Speicheroverhead hat liegt in der Rechnerarchitektur begründet, ansonsten wird es zwischen beiden keinen Unterschied geben.

Wer sich mit programmierbarer Hardware, also FPGAs auskennt weiß das man dort zb. mit den Sprachen VHDL, Verilog oder Abel sehr wohl ein Problem iterativ wie auch rekursiv beschreiben kann. Die nachfolgende Synthese wird in beiden Fällen das exakt gleiche Resultat erzeugen.

Die Unterscheide zwischen beiden sind also begründet in der Architektur der Hardware und nicht im Theoretischen. Auf zb. FPGAs verhalten sich beide gleich, benötigen identische Resourcen und sind identisch performant. Auf ASICs ändert sich dieses Verhältnis, aber je umfangreicher die Berechnungen werden desto mariginaler wird dieser Unterschied.

Ergo: man kann das iA. vernachlässigen und die Prioritäten anders legen. Nämlich auf Verständlichkeit und damit Wartbarkeit. Das Ändern des Algos., zb. ersetzen durch einen besseren, wird in fast allen Fällen bessere Resultate erzielen als sich auf diese mariginalen Unterschiede zu stürzen.

@Gammatester:

dein Vergleich hinkt: du vergleichst zwei unterschiedliche Lösungswege miteinander und schließt daraus das die iterative Version von Vorteil wäre.

Gruß Hagen

PS: übrigens berichte ich hier aus meinem 25jährigen Erfahrungsschatz und vertrete hier nur eine Meinung. Wer mich kennt weiß das ich der Letzte bin der nicht aus jedem Stück HW das letzte an Peformance rauszuholen versucht, und dh. eben auch das man einen Vergleich zwischen beiden Implementierungsmöglichkeiten praktisch durchführt.

[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

[Delphi-Laie]

Zitat:

Zitat von negaH (Beitrag 1028044)

Der einzige Grund warum eine rekursive Lösung unter Umständen einen leichten Performance-/Speicheroverhead hat liegt
in der Rechnerarchitektur begründet, ansonsten wird es zwischen beiden keinen Unterschied geben.

Ganz bestimmt nicht. Die Komplexität bzw. Effizienz von Algorithmen hat zunächst einmal überhaupt nichts mit ihrer Umsetzung zu tun.

Außerdem wurde mit der rekursiven Berechnung irgendeines Gliedes der Fibonacci-Folge diese pauschale Lobhudelei der Rekursion bereits widerlegt, denn dort wird jeder Zwischenwert doppelt, dreimal oder noch (viel) häufiger berechnet.