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 recht simpel in sein rekursives Pendant umgewandelt werden kann, ist der umgekehrte Weg meistens deutlich schwieriger. Oft ist es nur (?) möglich, indem eine für die Rekursion wichtige Speicherstruktur (der sog. Stack) nachgebildet („emuliert“) und anstatt des echten Stacks, der bei der Rekursion zum Zuge kommt, entsprechend verwendet wird. Allerdings ist auch diese Umwandlung grundsätzlich als gelungen anzusehen, weil die Hauptstruktur dann eine Schleife ist. Salopp könnte man solche Algorithmen als pseudorekursiv-stackiterativ (oder nur eines von beiden) bezeichnen. Vollendet ist diese Umwandlung erst, wenn auch dieser (Pseudo-)Stack entbehrlich wird. Beispiele dafür sind im Programm das Dekompositionsmerge und diverse Quicksorts.

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