# Ist Rekursion wirklich gefährlich? > [!tldr]- TL;DR > > Wenn Rekursion nicht richtig eingesetzt wird, werden bei jeder Iteration Daten auf den Stack gespeichert. Bei zu vielen Iterationen kann das schnell zu einem Stack Overflow führen. > > Stattdessen sollte eigentlich immer auf eine Schleifen-Implementation zurückgegriffen werden. ## Einführung Für unsere Fallstudie werden wir einen Algorithmus schreiben um die Fakultät (engl. Factorial) zu berechnen. Die Fakultät einer Zahl *n* ist das Produkt aller positiven natürlichen Zahlen die *n* nicht überschreiten. Diese Aufgabe können wir in einfache Schritte unterteilen: 1. *n* um eins verkleinern 2. bisheriges Produkt mit *n* multiplizieren 3. wiederholen bis *n* 0 ist Es gibt zwei Wege um diesen Algorithmus in C zu implementieren: Mit einer Schleife: ```C int factorial(int n) { int res = 1; while (n > 0) { res = res * n; n--; } return res; } ``` Mit Rekursion: ```C int factorial(int n) { if (n == 0) return 1; return factorial(n - 1) * n; } ``` Die Rekursive Funktion sieht eleganter aus. Ich möchte in diesem Blog jedoch genauer erklären warum es gefährlich sein kann, solche Rekursive Funktionen einzusetzen. ## Analyse Um das Problem zu verstehen müssen wir uns diesen Code in einem Tieferen Level ansehen. Da direkter Maschinen Code zu schwierig zu verstehen ist, werden wir x86 Assembly verwenden. Ich werde ausserdem die Intel Syntax verwenden, da es die meist verbreitete ist. > [!info]+ Assembly Einführung > > Assembly ist eine Low Level Programmiersprache. C wird beim Kompilieren zuerst zu Assembly Code übersetzt und anschliessend vom Linker und Assembler zu Maschinen Code umgewandelt. > > Es ist eine sehr komplexe Sprache mit vielen Konzepten. Für unsere Beispiel müssen wir jedoch nur die grundlegenden Konzepte verstehen. > > ## Register > >Wir sind es uns gewöhnt, unlimitierte Werte in Variablen speichern zu können. Diese Werte abzurufen ist jedoch ein aufwendiger und ineffizienter Prozess. Um in also zu beschleunigen, gibt es innerhalb des Prozessors vordefinierte Speicherorte namens Register. > >Um genau zu sein gibt es zehn 32-Bit und sechs 16-Bit Register: > >- EAX >- EBX >- ECX >- EDX >- EDI >- ESI >- EBP >- ESP >- E8 - E15 > >Was genau sie bedeuten ist zu umfangreich für diesen Blog und grundsätzlich können die meisten allgemein verwendet werden. Das einzige Register welches wir spezifisch verwenden werden ist EAX, in welchem das Return gespeichert wird. > >## Verschieben von Daten > >Um Daten zwischen Register zu verschieben verwenden wir den `mov` Befehl. Die meisten Operationen werden nach folgendem Format `befehl ziel, herkunft` geschrieben. Um also beispielsweise den Wert von EDI nach EAX zu verschieben wäre der Befehl: > >```nasm > mov eax, edi >``` > >Die Gross- und Kleinschreibung ist dabei irrelevant. > >## Grundlegende Berechnungen > >Die zwei Operationen die wir für unser Beispiel verwenden sind `imul` für Multiplikation und `sub` für Subtraktion. Die Operation wird auf das Zielregister angewendet. Um Beispielsweise EDI um 1 zu reduzieren wäre der Befehl: > >```nasm >sub edi, 1 >``` > >## Der Stack > >Das wichtigste Konzept für unsere Fragestellung ist der Stack. Im Stack können Daten zwischengespeichert werden, wenn sie nicht mehr in einem aktiven Register sein sollten. Er funktioniert gleich wie die bekannte Datenstruktur mit dem gleichen Namen (Daten werden am ende angehängt und können nur in der gleichen Reihenfolge wieder abgerufen werden). > >Für den Stack brauchen wir zwei Operationen: `push` und `pop`. `push` schreibt Daten aus einem Register in den Stack und `pop` entfernt sie endsprechend. > >Der Stack ist wichtig, jedoch nur sehr klein. Werden also zu viele Daten auf den Stack geschrieben, geschieht ein *Stack Overflow*. > >## Kommentare > >Single Line Kommentare können über ein `;` geschrieben werden. Übersetzen wir also unsere Rekursive Funktion in Assembly: ```nasm ; n = edi, ret = eax factorial: test edi, edi ; überprüft n == 0 jne nonzero ; springt zu nonzero wenn n nicht gleich 0 ist mov eax, 1 ; schiebt 1 in das Rückgaberegister ret ; gibt das Rückgaberegister zurück nonzero: push edi ; speichert n im Stack für spätere Multiplikation sub edi, 1 ; reduziert n um 1 call factorial ; ruft factorial auf pop edi ; lädt edi wieder aus dem stack imul eax, edi ; multipliziert das bisherige Produkt mit edi ret ``` Gehen wir diesen Code durch: Wir haben zwei Funktionen: *factorial* und *nonzero*. Gehen wir zuerst auf *nonzero* ein: Als erstes speichern wir den aktuellen Wert von *n* in den Stack. Dieser Schritt ist notwendig um am Ende die Multiplikation im `return factorial(n - 1) * n` durchführen zu können. Dann wir *n* um 1 reduziert und `factorial` aufgerufen. `factorial` überprüft ob n gleich 0 ist. Falls nicht ruft es wieder `nonzero` auf. Falls es 0 ist gibt es 1 zurück. In `nonzero` wird anschliessend das vorherige *n* wieder in ein register gespeichert und das Ergebnis von `factorial` damit multipliziert. Um es besser zu verstehen gehen wir das ganze manuell durch. Angenommen *n* ist 3: 1. *n* ist nicht 0 also rufen wir `nonzero` auf 2. Wir speicher *n* im Stack -> Stack = 3 3. Wir reduzieren *n* um 1 -> *n* = 2 4. Wir rufen `factorial` auf 1. *n* ist nicht 0 also rufen wir `nonzero` auf 2. Wir speichern *n* im Stack -> Stack = 3, 2 3. Wir reduzieren *n* um 1 -> *n* = 1 4. Wir rufen `factorial` auf 1. *n* ist nicht 0 also rufen wir `nonzero` auf 2. Wir speichern *n* im Stack -> Stack = 3, 2, 1 3. Wir reduzieren *n* um 1 -> *n* = 0 4. Wir rufen `factorial` auf 1. *n* ist gleich 0 2. Wir geben 1 zurück 5. Wir nehmen den obersten Wert vom Stack -> 1 6. Wir Multiplizieren den bisherigen Wert mit 1 -> 1 * 1 = 1 7. Wir geben es zurück 5. Wir nehmen den obersten Wert vom Stack -> 2 6. Wir multiplizieren den bisherigen Wert mit 2 -> 1 * 2 = 2 7. Wir geben es zurück 5. Wir nehmen den obersten wert vom Stack -> 3 6. Wir multiplizieren den bisherigen Wert mit 3 -> 2 * 3 = 6 7. Wir geben es zurück ### Das Problem Der Obige Code funktioniert und ist bei kleinen Zahlen auch kein Problem. Je grösser jedoch die Zahl, desto mehr Aufrufe von `nonzero` existieren gleichzeitig es. Bei jedem Aufruf wird das aktuelle *n* auf den Stack geschrieben. Entfernt wird es erst wieder, wenn der verschachtelte Aufruf fertig ist. Falls es noch nicht offensichtlich ist: Das Problem ist, dass bei jeder rekursiven Iteration ein neuer Wert auf den Stack geschrieben wird. Entfernt werden sie alle aber erst am Ende. Der Stack ist wie bereits erwähnt nur sehr klein. Hat man also zu viele Iterationen, schreibt man mehr Werte auf den Stack als Platz haben, was zu einem Stack Overflow führt. ### Die Lösung Es gibt zwei Möglichkeiten: Die Schleifen-Implementation zu verwenden oder die aktuelle Rekursion mit einer endständigen Rekursion zu ersetzen: ```C int factorial(int n, int p = 1) { if (n == 0) return p; return factorial(n - 1, p * n); } ``` So *returned* die Funktion direkt nach dem rekursiven Aufruf und muss nichts im Stack speichern. Vom Compiler würde das in eine einfache Schleife übersetzt werden. Ich werde nicht mehr im Detail darauf eingehen, aber der Assembly Code dafür wäre (ungefähr): ```nasm factorial: mov eax, 1 loop: imul eax, edi sub edi, 1 jne loop ret ``` ## Fazit Wir lernen also, Rekursion ist nicht immer böse, es muss jedoch extrem aufgepasst werden, dass nicht aus Versehen ein Stack Overflow verursacht wird. Grundsätzlich sollte Rekursion also nur verwendet werden, wenn man sich 100% sicher ist, dass man weiss was man macht. Ansonsten ist man immer auf der sicheren Seite mit einer Schleife.