Thema: Delphi Rekursion vs. Iteration

Einzelnen Beitrag anzeigen

Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#92

AW: Rekursion vs. Iteration

  Alt 13. Jun 2010, 13:10
@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
  Mit Zitat antworten Zitat