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.

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.

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

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;
}

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

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

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();
        }
    }
};

• 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 Syntax
• Standard Library & Units