Lyx – Rekursion

Rekursion ist ein Kontrollfluss-Muster, bei dem eine Funktion sich selbst aufruft, um ein Problem schrittweise auf einen einfacheren Fall zu reduzieren. Lyx unterstützt Rekursion auf allen Zielplattformen (x86_64, ARM64, RISC-V64) und bietet spezielle Werkzeuge zur Begrenzung und Verifikation des Stack-Verbrauchs – eine Voraussetzung für zertifizierungspflichtige Software nach DO-178C.

Jede rekursive Funktion besteht aus zwei Teilen:

• Basisfall – die Abbruchbedingung, die keine weiteren Aufrufe erzeugt
• Rekursionsschritt – der Aufruf mit einem vereinfachten Argument

unit rekursion;
import std.io;

// Klassisches Beispiel: Größter Gemeinsamer Teiler (Euklid)
fn GGT(a: int64, b: int64): int64 {
    if (b = 0) { return a; }      // Basisfall
    return GGT(b, a mod b);       // Rekursionsschritt
}

fn main(): int64 {
    PrintInt(GGT(48, 18));   // 6
    PrintInt(GGT(100, 75));  // 25
    return 0;
}

Der GGT ist ein ideales Einführungsbeispiel, weil jeder Rekursionsschritt das zweite Argument garantiert kleiner macht – die Termination ist damit mathematisch beweisbar.

Bei jedem rekursiven Aufruf legt der Compiler einen neuen Stack-Frame an. Dieser enthält die lokalen Variablen, die Rücksprungadresse und die gesicherten Register.

fn Factorial(n: int64): int64 {
    if (n <= 1) { return 1; }
    return n * Factorial(n - 1);
}

// Factorial(4) → Aufruf-Kette:

Factorial(4) ruft auf → Factorial(3) ruft auf → Factorial(2) ruft auf → Factorial(1)

Stack wächst abwärts:
┌──────────────────────────────┐  RSP (niedrige Adresse)
│ Frame: Factorial(1)  n=1     │  ← Basisfall: return 1
├──────────────────────────────┤
│ Frame: Factorial(2)  n=2     │  wartet auf Factorial(1) → 2 * 1 = 2
├──────────────────────────────┤
│ Frame: Factorial(3)  n=3     │  wartet auf Factorial(2) → 3 * 2 = 6
├──────────────────────────────┤
│ Frame: Factorial(4)  n=4     │  wartet auf Factorial(3) → 4 * 6 = 24
└──────────────────────────────┘  RBP (höhere Adresse)

Rückgabe: 24

Jeder Frame belegt mindestens 1 × int64 (8 Byte für n) + Rücksprungadresse (8 Byte) + gesicherte Register. Bei Factorial(1000) entstehen ~1000 Frames – ohne @stack_limit droht ein Stack-Overflow.

fn Fib(n: int64): int64 {
    if (n <= 1) { return n; }
    return Fib(n - 1) + Fib(n - 2);
}

Iterative Alternative (O(n), konstanter Stack):

fn FibIter(n: int64): int64 {
    if (n <= 1) { return n; }
    var a: int64 := 0;
    var b: int64 := 1;
    var i: int64 := 2;
    while (i <= n) {
        var tmp := a + b;
        a := b;
        b := tmp;
        i++;
    }
    return b;
}

fn BinSearch(arr: [512]int64, target: int64, lo: int64, hi: int64): int64 {
    if (lo > hi) { return -1; }          // nicht gefunden
    var mid: int64 := (lo + hi) / 2;
    if (arr[mid] = target) { return mid; }
    if (arr[mid] > target) {
        return BinSearch(arr, target, lo, mid - 1);
    }
    return BinSearch(arr, target, mid + 1, hi);
}

Maximale Rekursionstiefe: log₂(512) = 9 Ebenen – leicht verifizierbar und daher in @dal(C/D)-Modulen zulässig.

fn Pow(base: int64, exp: int64): int64 {
    if (exp = 0) { return 1; }
    if (exp mod 2 = 0) {
        var half := Pow(base, exp / 2);
        return half * half;
    }
    return base * Pow(base, exp - 1);
}

Tiefe: O(log exp) – Pow(2, 1024) benötigt nur ~20 Rekursionsebenen.

Eine Rekursion ist endrekursiv (tail-recursive), wenn der rekursive Aufruf die letzte Operation in der Funktion ist – kein weiteres Pending-Work wie eine Multiplikation nach der Rückkehr.

Der Lyx-Compiler erkennt Endrekursion automatisch und ersetzt call durch jmp (Jump). Dadurch wird kein neuer Stack-Frame angelegt; die Funktion läuft mit konstantem Stack-Verbrauch O(1).

// ✗ Kein TCO: Multiplikation (n * ...) nach dem rekursiven Aufruf
fn FactBad(n: int64): int64 {
    if (n <= 1) { return 1; }
    return n * FactBad(n - 1);   // Pending-Work: * n
}

// ✓ TCO: Akkumulator trägt den Zwischenstand mit
fn FactAcc(n: int64, acc: int64): int64 {
    if (n <= 1) { return acc; }
    return FactAcc(n - 1, n * acc);   // letzter Aufruf: kein Pending-Work
}

fn Factorial(n: int64): int64 {
    return FactAcc(n, 1);   // Einstieg mit Akkumulator 1
}

fn CountDown(n: int64) {
    if (n <= 0) { return; }
    PrintInt(n);
    CountDown(n - 1);   // Compiler erzeugt: jmp CountDown (kein call)
}

lyxc --emit-asm --trace-passes main.lyx | grep -A5 "CountDown"
# Erwartete Ausgabe:
# CountDown:
#   cmp rdi, 0
#   jle .exit
#   call PrintInt
#   dec rdi
#   jmp CountDown     ← kein 'call CountDown', sondern 'jmp'

Der GGT-Algorithmus (Abschnitt 1) ist bereits endrekursiv: GGT(b, a mod b) ist der letzte Aufruf ohne Pending-Work. Der Compiler wandelt ihn automatisch um.

Zwei oder mehr Funktionen können sich gegenseitig aufrufen (mutual recursion). Typisches Beispiel: Erkennung gerader/ungerader Zahlen oder gegenseitig rekursive Parser-Regeln.

// IsOdd nutzt IsEven, daher muss IsEven zuerst definiert sein
fn IsEven(n: int64): bool {
    if (n = 0) { return true; }
    return IsOdd(n - 1);
}

fn IsOdd(n: int64): bool {
    if (n = 0) { return false; }
    return IsEven(n - 1);
}

Rekursion ist das natürliche Werkzeug für das Traversieren rekursiver Datenstrukturen wie Bäumen und verketteten Listen.

unit bst;
import std.io;

type BSTNode = class {
    value: int64;
    left:  BSTNode?;
    right: BSTNode?;

    fn Create(v: int64) {
        self.value := v;
        self.left  := nil;
        self.right := nil;
    }

    fn Insert(v: int64) {
        if (v < self.value) {
            if (self.left = nil) {
                self.left := new BSTNode(v);
            } else {
                self.left.Insert(v);
            }
        } else {
            if (self.right = nil) {
                self.right := new BSTNode(v);
            } else {
                self.right.Insert(v);
            }
        }
    }

    fn Contains(target: int64): bool {
        if (self.value = target) { return true; }
        if (target < self.value) {
            return self.left?.Contains(target) ?? false;
        }
        return self.right?.Contains(target) ?? false;
    }

    fn Sum(): int64 {
        var leftSum  := self.left?.Sum()  ?? 0;
        var rightSum := self.right?.Sum() ?? 0;
        return self.value + leftSum + rightSum;
    }

    fn PrintInOrder() {
        self.left?.PrintInOrder();     // linker Teilbaum
        PrintInt(self.value);          // aktueller Knoten
        self.right?.PrintInOrder();    // rechter Teilbaum
    }

    fn Destroy() {
        self.left?.Destroy();
        self.right?.Destroy();
        dispose self;
    }
};

fn main(): int64 {
    var root := new BSTNode(50);
    root.Insert(30);
    root.Insert(70);
    root.Insert(20);
    root.Insert(40);

    root.PrintInOrder();           // 20 30 40 50 70
    PrintBool(root.Contains(40));  // true
    PrintInt(root.Sum());          // 210

    root.Destroy();
    return 0;
}

self.left?.Contains(target) nutzt den Safe-Navigation-Operator: Falls left nil ist, wird Contains nicht aufgerufen und ?? liefert den Fallback false.

type ListNode = class {
    value: int64;
    next:  ListNode?;

    fn Create(v: int64) {
        self.value := v;
        self.next  := nil;
    }

    fn Length(): int64 {
        return 1 + (self.next?.Length() ?? 0);
    }

    fn Reverse(): ListNode {
        // Basisfall: letzter Knoten wird neuer Kopf
        if (self.next = nil) { return self; }
        var newHead := self.next.Reverse();
        self.next.next := self;
        self.next := nil;
        return newHead;
    }
};

Unkontrollierte Rekursion kann den Stack erschöpfen. Lyx bietet zwei Mechanismen zur Kontrolle:

1. @stack_limit(N) – Pragma pro Funktion; setzt ein hartes Limit in Bytes
2. –stack-check – Compiler-Flag; prüft statisch den maximalen Stack-Verbrauch entlang des Call-Graphs

@stack_limit(2048)
fn Factorial(n: int64): int64 {
    if (n <= 1) { return 1; }
    return n * Factorial(n - 1);
}

Der Compiler berechnet den Stack-Bedarf pro Frame und multipliziert mit der maximalen Rekursionstiefe. Liegt der Wert über dem Limit, erzeugt er einen Fehler:

$ lyxc --stack-check main.lyx

✗ Stack-Limit verletzt: Factorial
  Frame-Größe:        24 Byte  (n: 8, ret-addr: 8, rbp: 8)
  Max. Tiefe:         200      (Eingabebereich n ≤ 200)
  Gesamt:             4800 Byte
  Limit (@stack_limit): 2048 Byte
  → Fehler: Erhöhe @stack_limit oder reduziere die maximale Rekursionstiefe.

Ist die Eingabe nicht statisch bekannt, kombiniert man @stack_limit mit einem expliziten Tiefenzähler:

@stack_limit(4096)
fn ParseExpr(depth: int64): int64 {
    if (depth > 64) {
        panic("Maximale Parse-Tiefe überschritten");
    }
    // ...
    return ParseTerm(depth + 1);
}

lyxc --stack-check --call-graph main.lyx

Stack-Analyse:
  GGT            →  max. Tiefe: log₂(max_input) ≈ 63,  Frame: 24 B  → ✅ 1512 B
  BinSearch      →  max. Tiefe: log₂(512)  = 9,         Frame: 48 B  → ✅  432 B
  Factorial      →  max. Tiefe: 200,                    Frame: 24 B  → ✗ 4800 B  (Limit: 2048)
  CountDown      →  TCO erkannt → Tiefe: 1 (O(1)-Stack) Frame: --   → ✅   --

Beim rekursiven Aufruf muss der Compiler die Register sichern, die nach dem Aufruf noch benötigt werden. Die Details hängen von der Zielplattform ab.

Factorial:
    stp  x29, x30, [sp, #-16]!   // Sichere Frame-Pointer (x29) und Link-Register (x30)
    mov  x29, sp
    // ... Körper ...
    bl   Factorial                // Rekursiver Aufruf: x30 wird überschrieben
    // ... x30 ist jetzt Adresse NACH diesem bl – korrekt durch stp gesichert
    ldp  x29, x30, [sp], #16     // Wiederherstellen
    ret

Ohne das stp x30 überschreibt der innere bl-Aufruf das Return-Address-Register – der äußere Aufruf kann nicht zurückspringen (häufigster Rekursions-Bug auf ARM64).

Faustregel: Rekursion verwenden, wenn das Problem natürlich rekursiv ist (Bäume, Parser, Divide & Conquer). Für lineare Folgen (Summen, Suche in Arrays) immer die iterative Form bevorzugen.

DO-178C und verwandte Standards stellen strenge Anforderungen an Rekursion in sicherheitskritischen Modulen.

@dal(B)
@flight_crit
@stack_limit(512)
unit parser;

// Maximale Grammatik-Tiefe ist durch das Protokoll auf 8 begrenzt.
// Nachweis: Dokument REQ-PARSE-MAX-DEPTH (rev 3)
fn ParsePacket(data: ^uint8, depth: int64): int64 {
    if (depth > 8) {
        return -1;   // Fehler statt panic – erlaubt in @flight_crit
    }
    var type_byte: uint8 := data^;
    if (type_byte = 0x01u8) {
        return ParseHeader(data, depth + 1);
    }
    if (type_byte = 0x02u8) {
        return ParsePayload(data, depth + 1);
    }
    return 0;
}

Der explizite depth-Parameter macht die maximale Rekursionstiefe für den Compiler und den Verifizierer sichtbar und prüfbar.

Merge-Sort ist ein klassischer Divide-&-Conquer-Algorithmus mit messbarer Rekursionstiefe O(log n).

unit mergesort;
import std.io;

fn Merge(arr: [1024]int64, lo: int64, mid: int64, hi: int64) {
    var left:  [512]int64;
    var right: [512]int64;
    var lLen := mid - lo + 1;
    var rLen := hi - mid;
    var i: int64 := 0;
    var j: int64 := 0;

    while (i < lLen) { left[i]  := arr[lo + i]; i++; }
    while (j < rLen) { right[j] := arr[mid + 1 + j]; j++; }

    i := 0;
    j := 0;
    var k := lo;
    while (i < lLen & j < rLen) {
        if (left[i] <= right[j]) {
            arr[k] := left[i]; i++;
        } else {
            arr[k] := right[j]; j++;
        }
        k++;
    }
    while (i < lLen) { arr[k] := left[i]; i++; k++; }
    while (j < rLen) { arr[k] := right[j]; j++; k++; }
}

@stack_limit(8192)
fn MergeSort(arr: [1024]int64, lo: int64, hi: int64) {
    if (lo >= hi) { return; }   // Basisfall: ein Element ist bereits sortiert
    var mid := (lo + hi) / 2;
    MergeSort(arr, lo, mid);        // linke Hälfte
    MergeSort(arr, mid + 1, hi);    // rechte Hälfte
    Merge(arr, lo, mid, hi);        // zusammenführen
}

fn main(): int64 {
    var data: [8]int64;
    data[0] := 38;  data[1] := 27;  data[2] := 43;  data[3] := 3;
    data[4] := 9;   data[5] := 82;  data[6] := 10;  data[7] := 1;

    MergeSort(data, 0, 7);

    var i: int64 := 0;
    while (i < 8) { PrintInt(data[i]); i++; }
    // Ausgabe: 1 3 9 10 27 38 43 82
    return 0;
}

Für n=1024: maximale Rekursionstiefe = log₂(1024) = 10 Ebenen – gut kalkulierbar für @stack_limit.

$ lyxc --stack-check --call-graph main.lyx

# Falls ein Overflow möglich ist:
✗ Rekursionstiefe für 'FibBad' nicht beschränkbar.
  Keine Terminationsgarantie nachweisbar (n kann beliebig groß sein).
  → Füge @stack_limit hinzu oder wandle in iterative Form um.

lyxc --debug --gl main.lyx && ./main

# Bei Stack-Overflow:
Runtime-Fehler: Stack-Overflow in 'Factorial'
  Stack-Trace:
    Factorial(n=1000) at main.lyx:5
    Factorial(n=999)  at main.lyx:5
    Factorial(n=998)  at main.lyx:5
    ... (997 weitere Frames)

Weiterführende Seiten:

• Memory Management – Stack, Heap, @stack_limit
• Schleifen – while, for, repeat-until
• Pattern Matching – match als Alternative zur Rekursion
• OOP – Rekursive Klassen und Datenstrukturen
• DO-178C – Stack-Nachweis und Call-Graph-Verifikation