Rekursion vs. Iteration

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