Rekursion vs. Iteration

[Delphi-Laie]

Zitat von alzaimar:

Ich kann mit Aussagen, wie "Rekursion ist per se langsamer als Iteration" nichts anfangen. Denn es ist Quatsch.

Natürlich. So pauschal eine solche Aussage ist, so falsch ist sie auch.

Mich würde in diesem Zusammenhang allerdings einmal interessieren, ob bei Problemlösungen, die sowohl iterativ als auch rekursiv möglich sind, es auch Fälle gibt, in denen die Rekursion hinsichtlich des Laufzeitverhaltens der Iteration substantiell (also vom Komplexitätsverhalten her) überlegen ist. Nachzuweisen, daß eine iterative einer (bestimmten) rekursiven Lösung überlegen ist, bedurfte es ja nur einer Folge, die schon seit dem späten Hochmittelalter (oder frühen Spätmittelalter) bekannt ist.

[jfheins]

Zitat von Delphi-Laie:

Mich würde in diesem Zusammenhang allerdings einmal interessieren, ob bei Problemlösungen, die sowohl iterativ als auch rekursiv möglich sind, es auch Fälle gibt, in denen die Rekursion hinsichtlich des Laufzeitverhaltens der Iteration substantiell (also vom Komplexitätsverhalten her) überlegen ist.

Ist unmöglich, da das Komplexitätsverhalten vom Algorithmus (also der Art der Problemlösung) und nicht von der Implementierung des Algorithmus (rekursiv/iterativ) abhängt. Du meinst schon das mit der Groß-O-Notation, oder? Denn ein rekursiver Quicksort und ein iterativer Quicksort haben beide eine Laufzeit von n*log(n) im Schnitt.

Zitat:

Nachzuweisen, daß eine iterative einer (bestimmten) rekursiven Lösung überlegen ist, bedurfte es ja nur einer Folge, die schon seit dem späten Hochmittelalter (oder frühen Spätmittelalter) bekannt ist.

Das "nachzuweisen" ist trivial.

Als Gegenbeispiel führe ich mal die Türme von Hanoi an: http://de.wikipedia.org/wiki/Türme_v...er_Algorithmus
Die rekursive Implementierung ist deutlich besser verständlich als die iterative. Beide haben natürlich das gleiche exponentielle Laufzeitverhalten.

Noch ein bereits genanntes Gegenbeispiel: Rekursiver Quicksort vs. iterativer Bubblesort. Sind ja beides Lösungen für das Sortierproblem - aber die rekursive Implementierung der Lösung ist deutlich schneller im Average Case

[Delphi-Laie]

Zitat von jfheins:

Zitat von Delphi-Laie:

Mich würde in diesem Zusammenhang allerdings einmal interessieren, ob bei Problemlösungen, die sowohl iterativ als auch rekursiv möglich sind, es auch Fälle gibt, in denen die Rekursion hinsichtlich des Laufzeitverhaltens der Iteration substantiell (also vom Komplexitätsverhalten her) überlegen ist.

Ist unmöglich, da das Komplexitätsverhalten vom Algorithmus (also der Art der Problemlösung) und nicht von der Implementierung des Algorithmus (rekursiv/iterativ) abhängt. Du meinst schon das mit der Groß-O-Notation, oder?

Ja.

Zitat von jfheins:

Zitat von Delphi-Laie:

Nachzuweisen, daß eine iterative einer (bestimmten) rekursiven Lösung überlegen ist, bedurfte es ja nur einer Folge, die schon seit dem späten Hochmittelalter (oder frühen Spätmittelalter) bekannt ist.

Das "nachzuweisen" ist trivial.

Als Gegenbeispiel führe ich mal die Türme von Hanoi an: http://de.wikipedia.org/wiki/Türme_v...er_Algorithmus
Die rekursive Implementierung ist deutlich besser verständlich als die iterative. Beide haben natürlich das gleiche exponentielle Laufzeitverhalten.

Ich meinte doch ausdrücklich, ob es eine schnellere rekursive Lösung gibt. Die Verständlichkeit ist unberührt.

Zitat von jfheins:

Noch ein bereits genanntes Gegenbeispiel: Rekursiver Quicksort vs. iterativer Bubblesort. Sind ja beides Lösungen für das Sortierproblem - aber die rekursive Implementierung der Lösung ist deutlich schneller im Average Case

Der Vergleich hinkt m.E. etwas. Es lassen sich zum einen auch rekursive (und auch iterative) Algorithmen finden, die langsamer als Bubblesort sind (Trippelsort, Slowsort), zum anderen gibt es auch iterative Sortieralgorithmen, die von der Geschwindigkeit her dem Quicksort wahrscheinlich mindestens ebenbürtig sind.

[xZise]

Moin,

Zitat von Delphi-Laie:

[...]Der Vergleich hinkt m.E. etwas. Es lassen sich zum einen auch rekursive (und auch iterative) Algorithmen finden, die langsamer als Bubblesort sind (Trippelsort, Slowsort), zum anderen gibt es auch iterative Sortieralgorithmen, die von der Geschwindigkeit her dem Quicksort wahrscheinlich mindestens ebenbürtig sind.

Dann fass dich bitte selber an die Nase: Du kannst einen schlechten rekursiv implementierten Algorithmus für die Fibonacci-Folge nicht mit einen optimierten iterativen Algorithmus vergleichen.

Das fib(n) := fib(n - 1) + fib(n - 2) nicht das beste Laufzeitverhalten hat, das hast du ja demonstriert, aber es gibt rekursive Implementierungen die sind so gut wie die iterativen. Ob das nun die ursprüngliche mathematische Definition ist, ist doch irrelevant, ob die rekursive Implementierung gut ist.

Und warum muss der rekursive Algorithmus unbedingt schneller sein? Solange sie gleich schnell sind passt das doch? Weil dann ist eine rekursive Implementierung meistens besser lesbar.

MfG
Fabian

[jfheins]

Zitat von Delphi-Laie:

Ich meinte doch ausdrücklich, ob es eine schnellere rekursive Lösung gibt. Die Verständlichkeit ist unberührt.

Wir drehen uns im Kreis

Bei Fibonacci habe ich dir eine rekursive Implementierung mit gleicher Komplexität gezeigt, die du wegen der verringerten Verständlichkeit (zu recht) abgelehnt hast. (Fibonacci ist eben ein Problem, dass man am besten per iteration löst)
Bei den Türmen von Hanoi habe ich dir gezeigt, dass rekursive Implementierungen bei gleicher Komplexität übersichtlicher sein können. Und du bestehst auf einer schnelleren Lösung ... schon die Entwicklung der iterativen Lösung die du jetzt nur auf Wikipedia angeguckt hast, hat wahrscheinlich Tage wenn nicht gar Wochen gebraucht, während die rekursive Variante schnell hingeschrieben ist.

[mkinzler]

Zitat:

Wir drehen uns im Kreis

Wir sind sozusagen Derwische

[Mithrandir]

Zitat von jfheins:

Wir drehen uns im Kreis

Das hab ich euch schon vor 15 Beiträgen versucht klar zu machen...

[negaH]

@Alzaimar

Zitat:

Das das nebenbei auch noch performanter ist, liegt an der Tatsache, das eine Schleife nun mal schneller ist

Das ist eben nicht richtig. Deine Aussage bezieht sich nur auf eine spezifische Hardware auf der dann Schleifen schneller laufen als zb. die gleiche Anzahl von Sprüngen zu Unterfunktionen.

Das gilt zb. für die Hardware FPGA oder Papier eben nicht mehr. Dort existiert kein Overhead im Speicher und Performance beim Aufruf von Unterfunktionen weil sie durch die Synthese eliminiert werden oder einfach nicht vorhanden sind.

Letzendlich sind es auch nicht "iterative" und/oder "rekursive" Verfahren. Sondern es ist ein und das selbe Verfahren das man schriftlich entweder iterativ oder rekursiv niederschreibt. Was am Ende in Hardware ankommt ist eine Frage der Compiler/Synthese und der Hardware selber.

Betrachtet man also die Frage "rekursiv vs. iterativ" unabhängig von Hardware dann sind sie identisch in ihrer Komplexität, Big O. Bezieht man die Hardware und Compiler etc.pp. mit in die Fragestellung ein dann muß man auch diese als Faktor berücksichtigen. Und erst da wird man dann leichte Nachteile der Rekursion gegenüber der Iteration haben wenn es sich zb. um ASICs handelt aber eben nicht bei FPGAs/CPLDs oder Quantenrechnern.

Dieser Overhead auf ASICs entsteht ausschließlich durch folgende Faktoren:
- zusätzliche CPU Takte sind nötig bei Sprüngen
- zusätzlicher Stack ist nötig zum Speichern der Rücksprungadresse und Einrichten des Stackframes der rekursiven Unterfunktion
- zusätzliche CPU Takte sind nötig für diese Stackeinrichtung und Stackbereinigung
- ein RET zum Aufrufer ist nötig

Das sind alles nur Faktoren auf Grund der CPU Architektur die eben Sprünge benachteiligt zu Programmcode der ohne diese auskommt wie bei iterativen Umsetzungen.

Als letztes kommt noch der Punkt hinzu das zb. der Delphi Compiler nicht über Funktionsrümpfe hinweg optimieren kann. Er wird also besser eine iterative Funktion optimieren können als deren rekursve Schreibweise.

Das alles sind aber Punkte die man bei der generellen Bewertung "iterativ vs. rekursiv" aussen vor lassen muß. Und dann ergibt sich wieder das gewohnte mathematische Bild das beide äquvivalente Schreibweisen der selben Sache sind und nichts mehr.

Wenn dem so ist wird nun auch logsich das man sich bei dieser Frage nur auf die Fragestellung: was ist verständlicher beziehen darf. Und das hängt letzendlich vom Algorithmus und der Zielsetzung ab. Bei bestimmten, wenigen Problemen ist die iterative Schreibweise einfacher zu verstehen, bei den meisten Problemen wird aber schon bei der Mathematik und deren Formel die rekusive Schreibweise bevorzugt da sie intuitiver und einfacher ist. Vernachlässigt man also mal den mariginalen Performance/Speicheroverhead der auf ASICs systembedingt einen Unterschied ausmacht dann ist in den meisten Fällen die rekursive Schreibweise die bessere Wahl. Nicht weil sie schneller sein könnte oder weniger Speicher verbraucht, das haben wir ja nun hinlänglich ausdiskutiert das dies nicht der Fall sein kann und darf, sondern weil sie angemessener ist und verständlicher.

Gruß Hagen

[negaH]

Zitat:

Das gilt zb. für die Hardware FPGA oder Papier eben nicht mehr. Dort existiert kein Overhead im Speicher und Performance beim Aufruf von Unterfunktionen weil sie durch die Synthese eliminiert werden oder einfach nicht vorhanden sind.

Betrachtet man mal die Harwdare Papier genauer in diesem Rahmen dann sind rekursive Scheibweisen sogar Speicher=Papier schonender als die meisten iterativen Schreibweisen. In diesem Fall kann man unter Berücksichtung "Harwdare ist Papier" sogar behaupten das rekursive Schreibweisen besser sind als iterative. Auch die Resource "Performance" ist in diesem Fall besser da man weniger Formeln eben schneller schreiben kann als mehr Formeln.

Gruß Hagen

[JasonDX]

Zitat von Delphi-Laie:

Mich würde in diesem Zusammenhang allerdings einmal interessieren, ob bei Problemlösungen, die sowohl iterativ als auch rekursiv möglich sind, es auch Fälle gibt, in denen die Rekursion hinsichtlich des Laufzeitverhaltens der Iteration substantiell (also vom Komplexitätsverhalten her) überlegen ist.

Ich tendiere zu nein. Sollte ich die Zeit dafür finden, ließe sich evt. ein Beweis für die Äquivalenz beider Verfahren finden.

Zitat von Delphi-Laie:

Nachzuweisen, daß eine iterative einer (bestimmten) rekursiven Lösung überlegen ist, bedurfte es ja nur einer Folge, die schon seit dem späten Hochmittelalter (oder frühen Spätmittelalter) bekannt ist.

Ein klares Zeichen, dass du Beiträge entweder nicht liest oder nicht verstehst. Es ist bereits gezeigt worden, dass die iterative Lösung der rekursiven nicht überlegen ist. Tailrecursion is recursion! Bitte lese zukünftig Beiträge, bevor du ihnen widersprichst.

greetz
Mike