Rekursion vs. Iteration

[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