if (c like recursion)

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 1-Zeiler 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 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 Addressbereich 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?


Wenn sich eine triviale Erkenntnis mit Dummheit in der Interpretation paart, dann gibt es in der Regel Kollateralschäden in der Anwendung.
frei zitiert nach A. Van der Bellen
... also dann paaren wir mal eine komplexe Erkenntnis mit Klugheit in der Interpretation!