====== Lyx – Rekursion ======

Lyx unterstützt die volle **rekursive Funktionsaufrufe**. Da der Compiler die Standard **Linux x86_64 SysV ABI** implementiert, nutzt jeder Aufruf den Hardware-Stack, um Rücksprungadressen und lokale Variablen (Stack-Frames) sicher zu verwalten.

----

===== 1) Grundlagen =====

Eine Funktion wird als rekursiv bezeichnet, wenn sie sich innerhalb ihres eigenen Körpers selbst aufruft. In Lyx erfordert eine saubere Rekursion zwei Bestandteile:
  * **Abbruchbedingung (Base Case):** Ein Pfad, der keinen weiteren rekursiven Aufruf tätigt.
  * **Rekursionsschritt:** Der Aufruf der Funktion mit veränderten Argumenten, die dem Base Case näher kommen.

==== Beispiel: Fakultät (Factorial) ====

Die mathematische Fakultät (n!) ist das klassische Beispiel für Rekursion:

<code lyx>
fn Factorial(n: int64): int64 {
    // 1. Abbruchbedingung
    if (n <= 1) {
        return 1;
    }
    // 2. Rekursiver Schritt
    return n * Factorial(n - 1);
}

fn Main(): int64 {
    var result: int64 := Factorial(5);
    PrintStr("5! ist: ");
    PrintInt(result); // Ausgabe: 120
    return 0;
}
</code>

----

===== 2) Technische Implementierung =====

==== Stack-Frame Management ====

Bei jedem rekursiven Aufruf erzeugt das Backend einen neuen **Stack-Frame**. Dies garantiert, dass jede Instanz der Funktion ihre eigenen lokalen Variablen besitzt.



^ Schritt ^ Aktion im Backend ^ Register / Stack ^
| **Proloque** | Sichern des alten Base-Pointers | `push rbp`, `mov rbp, rsp` |
| **Arguments** | Parameter für den nächsten Aufruf setzen | `mov rdi, [new_val]` |
| **Call** | Rücksprungadresse speichern & springen | `call Factorial` |
| **Epilogue** | Stack aufräumen & zurückkehren | `leave`, `ret` |

==== Status der Optimierung ====

^ Feature ^ Status ^ Beschreibung ^
| **Hardware-Stack** | ✅ Aktiv | Volle Nutzung des RSP-Registers. |
| **Register-Safety** | ✅ Aktiv | Caller-saved Register werden vor dem Aufruf gesichert. |
| **Tail-Call Opt.** | 🚧 Geplant | Aktuell wird für jeden Aufruf ein neuer Frame erzeugt (keine Ersetzung). |

----

===== 3) Rekursion in Datenstrukturen (v0.1.7) =====

Mit der Einführung von Klassen können nun rekursive Methoden auf Objekten definiert werden, was ideal für Baumstrukturen oder verkettete Listen ist.

<code lyx>
type Node = class {
    Value: int64;
    Next: Node?; // Nullable Pointer

    fn PrintAll() {
        PrintInt(self.Value);
        PrintStr(" ");
        
        // Rekursiver Aufruf auf das nächste Element
        if (self.Next != null) {
            self.Next?.PrintAll();
        }
    }
};
</code>

----

===== 4) Wichtige Hinweise & Limits =====

  * **Stack Overflow:** Da Lyx keinen unendlichen Stack hat, führt eine zu tiefe Rekursion (oder eine fehlende Abbruchbedingung) zu einem **Segmentation Fault**. Das Limit liegt unter Linux standardmäßig bei 8 MB.
  * **Performance:** Rekursion ist elegant, aber für extrem einfache Aufgaben (wie bloßes Zählen) ist eine iterative Lösung (while-Schleife) effizienter, da der Overhead des Funktionsaufrufs entfällt.

----
**Verwandte Themen:**
  * [[lyx_-_programmiersprache:syntax|Lyx Syntax]]
  * [[lyx_-_programmiersprache:standard_library|Standard Library & Units]]