Iterativ versus rekursiv

Die Grundstruktur jedes Sortieralgorithmus' besteht entweder aus Schleifen (iterativ) oder im Sich-Selbst-Aufrufen bestimmter Unterprogramme oder gar der eigentlichen Sortierroutine (rekursiv). Oft können diese Strukturen adäquat ineinander transformiert werden, sie sind dann äquivalent, was sich auch in (zumindest nahezu) gleicher Sortiergeschwindigkeit zeigt. Ein sehr einfaches und entsprechend bekanntes Beispiel liefert die Berechnung der Fakultät.

Während jeder iterative (nicht nur Sortier-)Algorithmus in sein rekursives Pendant umgewandelt werden kann, ist bei bestimmten rekursiven Algorithmen, so z.B. dem Quicksort, die Umwandlung in einen iterativen nur trickreich und unvollständig möglich, nämlich indem eine für die Rekursion wichtige Speicherstruktur (der sog. Stack) nachgebildet („emuliert“) und anstatt dieses Stacks entsprechend verwendet wird. Allerdings ist auch diese Umwandlung grundsätzlich als gelungen anzusehen, weil die Hauptstruktur dann eine Schleife ist.

Um die simultanen / parallelen / Multithreadingalgorithmen hinsichtlich der Anzahl zu sortierender Elemente möglichst uneingeschränkt nutzen zu können, war es nötig, den während der Programmlaufzeit leider konstanten sog. Stackspeicher des Programmes (und damit aller seiner Threads) soweit wie möglich zu reduzieren. Dieser wird jedoch für die Rekursionen benötigt, sodaß das Programm dann ggf. wegen (Stack-)Speichermangels abbricht. Infolgedessen wandelte ich die allermeisten Rekursionen in Iterationen um. Die Grundideen dazu (nötige Stack-Ersatzsspeicherstruktur, Methodik der Umwandlung) entnahm ich Robert Sedgewicks Buch „Algorithmen“. Diese Transformation hat keinen signifikanten Einfluß auf die Laufzeit und überhaupt keinen auf die Animation der Algorithmen.

Die Rekursion bei Sortieralgorithmen wird gern und bevorzugt zur Realisierung des sog. Verteile-und-herrsche-Prinzips („divide et impera“) verwendet.

Kontaktformular