Zitat von
alzaimar:
Zurück zum Thema:
Ich hab mal eine iterative Quicksortvariante geschrieben, weil ich es einfach mal wissen wollte (so wie beim Ackermännchen):
Bei kleinen N ist die rekursive Implementierung doch schneller, bei großen N die Iterative.
Bei der ganzen Diskussion fehlt mir zunächst einmal die Definition: "was ist rekursiv?"
Sicher kann ich Quicksort ohne eigenen Funktionsaufruf hinschreiben, indem ich von den zwei Teilsegmenten einen auf einen Stack lege und mit dem zweiten direkt weitermache. Nichtsdestotrotz ist der
Algorithmus rekursiv, denn das Problem wird dadurch gelöst, dass man auf zwei kleinere Teilabschnitte dasselbe Verfahren anwendet. Ob ich das nun über den CPU-Stack löse (Aufruf) oder den Stack selbst implementiere ändert nichts an der Verfahrensweise des Algorithmus.
Du (aber nicht alleine) hattest in dem anderen Thread ja mal als Beweis angeführt, dass eine CPU immer iterativ arbeitet und somit, sofern jeder rekursive Algorithmus implementiert werden kann, die Übersetzung in eine (iterative) Maschinensprache beweist, dass er iterativ ausgeführt werden kann. Ich hatte dann ja eine kleine rekursive Assemblerroutine hingeschrieben.
Allerdings ist es hier doch nur eine Schreibweise. Einen Unterschied darin zu sehen, ob eine Routine sich mit "call" selbst aufruft oder die Werte mit "push" auf den Stack legt und dann mit "jmp" wieder zum Start springt, ist doch eigentlich Haarspalterei.
Zurück zum Thema: für mich kommt es also nicht auf die Implementierung an sondern auf die Funktionsweise. Und hier ist jeder Algorithmus rekursiv, der nach "Divide and Conquer" verfährt und zur Lösung des Problems wieder den Algorithmus selbst auf Teilbereiche anwendet.
(los, zerreisst mich
)