Rekursion Ist Gut

Rekursion ist besser als ihr Ruf⌗

An zahlreichen Literaturstellen wie auch in Unterlagen aus dem Internet ist immer wieder die Rede davon, dass Rekursion etwas Schlechtes sei und vermieden werden soll. Gleichzeitig gibt es wahrscheinlich keine einzige Universität auf diesem Erdball, an der Rekursion nicht gelehrt wird. Diesen vermeintlichen Widerspruch, dass Dinge gelehrt werden, die man nicht nutzen soll, sind wir auf den Grund gegangen.

Was ist Rekursion überhaupt?⌗

Rekursion ist in der Informatik ein Programmiertrick, bei dem sich eine Funktion oder Methode immer wieder selbst aufruft.

int fak(int n) {
    if(n==1)
        return 1;
    else
        return n * fak(n-1);

Anwendung findet dieser Trick in zahlreichen mathematischen Funktionen, wie beispielsweise die Berechnung der Fakultät oder der Fibonacci-Folge. Ebenso wird Rekursion für die Definition von Wiederholungen in einer Sprachgrammatik in der Backus-Naur-Form benötigt oder beispielsweise für die Detektion von Palindromen verwendet. Vor diesem Hintergrund wäre doch anzunehmen, dass Rekursion eine tolle Lösungsmöglichkeit für komplexe Fragestellungen ist. Ist sie auch. Doch zunächst müssen wir Aufklärungsarbeit leisten.

Warum behaupten manche, dass Rekursion böse ist?⌗

Das Hauptargument der Gegner der Rekursion berufen sich darauf, dass bei Rekursion die lokalen Funktionsvariablen auf dem Stapelspeicher (Stack) bei jedem geschachtelten Aufruf nicht abgeräumt werden und dadurch der Stack unendlich anwächst. Voller Sorge verweisen die Gegner darauf, dass der vermeintlich unendlich wachsende Stack immer in den Heap hineinwächst und dort unsere verzeigerten Daten korrumpiert.

Was sind die Alternativen?⌗

Rekursionsgegner führen an, dass sich jede Rekursion auch durch eine iterative Implementierung mit while() oder for() lösen lässt. Das Resultat sind dann aber meist unübersichtliche und fehlerträchtige for()-Ungetüme, die kaum zu verstehen sind und oft genug mit off-by-one-Fehlern einhergehen. Mit den ursprünglichen rekursiven Formeldefinition haben diese Lösungen nichts mehr gemein. Verständlichkeit und Wartbarkeit leiden, dabei sind Verständlichkeit und Wartbarkeit Eigenschaften von gutem Code, die man nicht opfern sollte.

Was der Compiler draus macht⌗

Compiler sind heute so clever, dass sie viele der Vorurteile der Rekursion gar nicht erst eintreten lassen. Bereits seit vielen Jahren erkennen Compiler Rekursion und optimieren den Output durch partielles Stack-Unwinding vor der Rekursion so, dass das Stack-Wachstum minimal ist. Bei Tail-Recursion, wo die Rekursion Teil der Rückgabe ist, findet in der Realität überhaupt kein Stack-Wachstum mehr statt.

Warum ist der Stack überhaupt ein immer wiederkehrendes Problem?⌗

Schauen wir uns zunächst die Default-Größen der Stacks an: Unter x86-Linux sind es typischerweise 8MB, auf Windows 10 sind es gerade mal 2MB und unter Threads, die unter IIS ASP.net ausführen sogar nur erbärmliche 256kB. Vor dem Hintergrund typischer heutiger Systeme mit zum Teil dutzenden Gigabyte an RAM sind solche Stack-Größen geradezu lächerlich klein bemessen. Langjähriges blindes Befolgen von falschen Ratschlägen der Rekursionsgegner, gepaart mit lächerlich kleinen Default-Stackgrößen hat branchenweit den Entwicklern eingebläut, konsequent alle Objekte auf dem Heap anzulegen, statt sie dort zu belassen, wo sie eigentlich hingehören. Unleserliche &*->-Orgien, die kaum noch ein Entwickler versteht, waren die Folge.

So gefährlich sind malloc() und new()⌗

Heap-Speicher soll nun also als Ersatz dienen für einen Stack, der einfach nur zu klein bemessen ist. Heap-Speicher wird unter C++ meist durch new() bereitgestellt, unter C meist mit malloc(). Das Ergebnis ist eine Referenz auf einen Speicherort, wo man nun seine Daten hinräumen kann. Die konkrete Speicherstelle wird über eine Runtime-Bibliothek berechnet, die auch garantiert, dass jede belegte Speicherstelle auch nur ein einziges Mal vergeben wird. Diese Logik ist aufwändig und kostet jede Menge CPU-Zyklen, was den Code langsam werden lässt. Zugleich liegen die Speicherstellen mit der Zeit zusehends verstreut im RAM, so dass im ungünstigen Fall selbst bei vermeintlich viel freiem Speicher sich aber kein zusammenhängender Speicher mehr finden lässt: Speicherfragmentierung führt selbst bei großem Speicher zu künstlichem Speichermangel. Man kann sich fragen, ob hier nicht Interessenspolitik der Speicher-Hersteller im Spiel war. Darüber hinaus muss bei Einsatz von Heap-Speicher im Code stets über eine Indirektion durch Pointer und mit Pointer-Dereferenzierung gearbeitet werden. Pointer-Arithmetik gilt nicht ohne Grund als außerordentlich kritisch und fehleranfällig. Man kann zudem leicht den Eindruck gewinnen, dass 30% aller Entwickler Pointer überhaupt nicht verstehen, und diese dann einfach so lange Sterne, Und-Zeichen und Pfeile an ihre Objekte drankleben, bis es halt irgendwann mal funktioniert. Hier ein typisches Beispiel für Code von einem Entwickler, der offensichtlich seine liebe Not mit Pointern hatte:

// Hate this!
// Why do callers pass this star thing as arg?
int func (int* arg) {
    // my colleague advised me to do some conversion
    void* val = &*&(*((void*)&*arg));
    // don’t touch – it works somehow
    return fak(*(int*)*&arg);
}

Die Lösung für sichere Rekursion⌗

Doch zurück zum eigentlichen Thema Rekursion: Um Rekursion sicher zu machen, müssen wir lediglich die viel zu kleinen Default-Werte der Stacks anpassen. Das ist ganz leicht: In Visual Studio kann man die Stack-Größe unter Projekt -> Eigenschaften -> Linker -> Alle Optionen -> Stapelreservierungsgröße einfach anpassen.

Hier wird auch ersichtlich, das Visual Studio 2019 dem Programm gerade einmal 1MB Speicher gönnen will. Da mein System 32GB hat, gönne ich meinem Programm hier 1 GB und erspare mir damit jegliche Sorge mit Pointern oder Stack-Überläufe durch Rekursion. Da der Speicher auf dem Stack auch effizienter angeordnet ist als auf einem verstreuten Heap, verbraucht das Programm am Ende auch weniger RAM.

Was mache ich mit Programmen, die als Binary vorliegen?⌗

Kein Problem! Da die Stack-Größe erst zum Start des Programms eine Relevanz bekommt, kann man den Wert in einem Binary auch noch nachträglich mit dem Kommandozeilentool editbin anpassen. Mit dem Aufruf von dumpbin /headers myprogram.exeerhalten wir eine Auflistung von Meta-Informationen, darunter in der Zeile size of stack reserve auch die Informationen zur Stack-Größe. Mit dem Aufruf editbin /STACK:1GB myprogram.exe bescheren wir dem Programm auch nachträglich mehr Platz auf dem Stack.

Fazit⌗

Rekursion hat völlig zu Unrecht einen schlechten Ruf. Beim richtigen Einsatz seiner Entwicklungswerkzeuge lässt sich jede Rekursion durch Vergrößern des Stacks sicher machen. Mit großen Stacks lassen sich darüber hinaus auch die gefährlichen Pointer vermeiden und der Speicher effizienter nutzen. Rekursion ist also gut!