if (c like recursion)
« | 02 Nov 2018 | »Da hatte mal ein pfiffiger Kerl einen Code für eine Wildcard - Suche verfasst, der mein C-Fanboy-Herz schneller schlagen lässt.
Wenn man eine komplexere Suche in eine Zeile bannen kann, die auch noch
korrekt funktioniert, ist das schon was sehr Schönes.
Und die besonderen Nebeneffekte sind:
- Sehr geringer Maschinencode
- Portabel auf alle (und zwar wirklich alle) Plattformen
- Man kann damit Wettbewerbe gewinnen
Und wie hat der Junge das geschafft?
Mit einer Rekursion.
Also stellte ich mir die Frage, ob ich diesen Code nicht selbst
einsetzen soll.
Doch die Antwort lautete: Nein.
Warum?
Na wegen der Rekursion!
Tiefe Rekursionen führen gerne mal dazu, dass einem der Stack ausgeht bzw. überläuft.
Üblicherweise stellen uns die heutigen Betriebssysteme 1 MegaByte Stack pro Thread zur Verfügung, der manchmal bei Bedarf auch wachsen kann.
Da jeder Funktionsaufruf ein neues Stack-Frame erzeugt, das erst beim Beenden der Funktion wieder freigegeben wird, belegen tiefe Rekursionen linear immer weiter Speicher.
Und der oben erwähnte Einzeiler lässt für jede einzelne Zeichenprüfung
die Funktion neu aufrufen.
Aber keine Sorge. Der Code kann so umgebaut werden, dass alle Nicht-Sternchen-
Vergleiche in einer Schleife abgearbeitet werden und nur jedes neue Sternchen
die Funktion rekursiv aufruft.
Und schon haben wir eine einfache portable
Like
Implementierung, so wie ich sie auch damals in
VB in Erinnerung habe.
Für mich stellt sich dann eine allgemeinere Frage: Wo sind Rekursionen gut und wo nicht? Was sind die Alternativen?
In der C++ Metaprogrammierung sind tiefe Rekursionen oft gar kein Problem und meist alternativenlos. Aber nachdem der Compiler diese Metakonstrukte während des Kompilierenes auflöst, sollten wir im Normalfall keinen Code erhalten, der Stacks überlaufen lässt.
In der regulären Programmierung ist die Tiefe entscheidend. Besteht die Gefahr, dass eine Funktion sich 1000e Male selbst in einer Kette aufruft, sollte man sich Alternativen überlegen. Im schlimmsten Fall kann man die Stack-Rekursion immer auf den Heap auslagern. Anstatt eines neuen Funktionsaufrufes beginnt man ein neues “Heap-Frame” in einer hochzählenden Liste, wo alle lokalen Variablen gespeichert sind und lässt seine Funktion in einer Schleife laufen.
Wenn Rekursionen keine besondere Tiefe Erreichen, sind sie natürlich immer erlaubt. Der Klassiker ist das Durchlaufen aller Ordner eines Dateisystems.
Fazit
Rekursionen also bitte immer mit Bedacht einsetzen!
…außer man möchte einen Programmierwettbewerb gewinnen. Da kann man schon mal so cool sein, und Stacklimits ignorieren.
Denken wir an DOS zurück:
In einem *.COM - Program waren Code und Stack in einem
64 KiloBytes Segment untergebracht. Der Stack wächst hier dem Code entgegen.
Mit einer Rekursion kann es also passieren, dass ausführbarer Code vom
Stack überschrieben wird.
… doch wer hätte damals daran gedacht, dass Programme, die 1 KiloByte groß sind jemals so viele Daten bearbeiten müssen, dass der Stack den Codebereich berührt?
Wenn ich es recht im Kopf habe, versuchen Linux und Windows den Stack im Adressbereich unterhalb des ausführbaren Codes zu platzieren … somit können Stacks rein technisch nie den Code berühren.
Nachtrag: Mein schlimmstes Erlebnis in Sachen Rekursionen ist und bleibt die Aussage eines “fertigen” Informatik-Studenten, der meinte: “Ich kann mir überhaupt nicht vorstellen, wie so eine Rekursion überhaupt funktionieren kann. Wie können da brauchbare Ergebnisse rauskommen?”
Als Autodidakt atmet man dann tief durch und fragt sich: Wer prüft die Prüfer an unseren Hochschulen?