====== 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.

===== 1. Grundlagen =====

Jede rekursive Funktion besteht aus zwei Teilen:

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

<code lyx>
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;
}
</code>

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

===== 2. Call-Stack-Visualisierung =====

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.

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

// Factorial(4) → Aufruf-Kette:
</code>

<code>
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
</code>

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.

===== 3. Klassische Beispiele =====

==== Fibonacci ====

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

<box gh>
> **Achtung – Exponentielles Wachstum:**
> Die naive Fibonacci-Rekursion hat die Zeitkomplexität **O(2ⁿ)**. Fib(40) erzeugt über eine Milliarde Aufrufe. Für n > 30 immer die iterative Version oder Memoization verwenden.
</box>

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

<code lyx>
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;
}
</code>

==== Binäre Suche (rekursiv) ====

<code lyx>
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);
}
</code>

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

==== Potenz (schnelle Exponentiation) ====

<code lyx>
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);
}
</code>

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

===== 4. Tail-Call Optimization (TCO) =====

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)**.

==== Nicht TCO-fähig vs. TCO-fähig ====

<code lyx>
// ✗ 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
}
</code>

==== CountDown – einfaches TCO-Beispiel ====

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

==== TCO in der Ausgabe prüfen ====

<code bash>
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'
</code>

==== GGT mit TCO ====

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.

===== 5. Gegenseitige Rekursion =====

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

<code lyx>
// 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);
}
</code>

<box gh>
> **Hinweis:**
> Gegenseitige Rekursion ist selten TCO-optimierbar (der Compiler müsste beide Funktionen gemeinsam analysieren). Für tiefe gegenseitige Rekursion bevorzugt man einen expliziten Stack (iterativ) oder ein Trampolin-Muster.
</box>

===== 6. Rekursion auf Datenstrukturen =====

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

==== Binärer Suchbaum (BST) ====

<code lyx>
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;
}
</code>

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

==== Verkettete Liste ====

<code lyx>
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;
    }
};
</code>

===== 7. Stack-Verbrauch & @stack_limit =====

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

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

==== @stack_limit ====

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

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

<code>
$ 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.
</code>

==== Maximale Tiefe einschränken ====

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

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

==== --stack-check Gesamtbericht ====

<code bash>
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: --   → ✅   --
</code>

===== 8. Architektur: Calling Convention bei Rekursion =====

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.

^ Architektur ^ Rücksprung-Register ^ Sicherung bei Rekursion ^ Alignment ^
| x86_64 | Stack (implizit via ''call''/''ret'') | Callee-saved: RBX, R12–R15, RBP | 16 Byte |
| ARM64 | Link Register X30 | X30 muss auf Stack gerettet werden | 16 Byte |
| RISC-V64 | Return Address ''ra'' | ''ra'' muss im Prolog gesichert werden | 16 Byte |

==== ARM64 Prolog bei Rekursion ====

<code>
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
</code>

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**).

===== 9. Rekursion vs. Iteration =====

^ Kriterium ^ Rekursion ^ Iteration ^
| Lesbarkeit | Oft klarer bei baumartig strukturierten Problemen | Klarer bei linearen Folgen |
| Stack-Verbrauch | O(Tiefe) – kann Stack sprengen | O(1) – konstant |
| TCO-Optimierung | O(1) bei endrekursiver Form | Immer O(1) |
| Performance | Aufruf-Overhead (ohne TCO) | Minimal (simpler Sprung) |
| Einsatz in @flight_crit | Nur mit nachgewiesener Maximaltiefe | Bevorzugt |
| Debugging | Stack-Trace zeigt Aufrufkette | Nur aktuelle Position |
| Typische Anwendung | Bäume, Graphen, Parser, Divide & Conquer | Schleifen, Summen, Iteration |

**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.

===== 10. Rekursion in Safety-Code =====

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

^ Bedingung ^ @dal(A) ^ @dal(B) ^ @dal(C/D) ^
| Endrekursion (TCO, O(1)-Stack) | ✅ Erlaubt | ✅ Erlaubt | ✅ Erlaubt |
| Nachgewiesene Maximaltiefe + @stack_limit | ⚠️ Mit Nachweis | ✅ Erlaubt | ✅ Erlaubt |
| Unbeschränkte Rekursion | ❌ Verboten | ❌ Verboten | ⚠️ Warnung |
| Gegenseitige Rekursion (mutual) | ❌ Verboten | ⚠️ Mit Nachweis | ⚠️ Warnung |
| ''--call-graph''-Report erforderlich | ✅ Pflicht | ✅ Pflicht | – |

==== Empfohlenes Muster für @dal(B) ====

<code lyx>
@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;
}
</code>

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

===== 11. Vollständiges Beispiel: Merge-Sort =====

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

<code lyx>
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;
}
</code>

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

===== 12. Debugging & häufige Fehler =====

==== Stack-Overflow diagnostizieren ====

<code bash>
$ 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.
</code>

==== Häufige Fehler ====

^ Fehler ^ Ursache ^ Lösung ^
| Stack-Overflow (Segfault) | Basisfall fehlt oder wird nie erreicht | Abbruchbedingung prüfen; Eingabe validieren |
| Falsche Ergebnisse auf ARM64 | Link-Register X30 nicht gesichert | Compiler-Bug: fehlendes ''stp x29, x30'' im Prolog |
| Stack-Overflow auf ARM64 bei 16-Byte-Grenze | Ungerader Stack vor ''bl'' | Compiler: RSP-Alignment-Prüfung im Prolog aktivieren |
| Unresolved Jump Patches | Emitter erkennt Eigenaufruf nicht als intern | ''--trace-passes'' prüfen; Symbol-Tabelle vollständig? |
| Exponentiell langsam | Naive Rekursion ohne Memoization | Iterative Form oder Akkumulator-Pattern verwenden |
| Gegenseitige Rekursion – TCO fehlt | Compiler analysiert nur einzelne Funktionen | Trampolin-Pattern oder iterativen Dispatcher verwenden |

==== Stack-Trace im Debug-Build ====

<code bash>
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)
</code>

**Weiterführende Seiten:**
  * [[lyx_-_programmiersprache:memory-management|Memory Management – Stack, Heap, @stack_limit]]
  * [[lyx_-_programmiersprache:schleifen|Schleifen – while, for, repeat-until]]
  * [[lyx_-_programmiersprache:pattern-matching|Pattern Matching – match als Alternative zur Rekursion]]
  * [[lyx_-_programmiersprache:oop|OOP – Rekursive Klassen und Datenstrukturen]]
  * [[lyx_-_programmiersprache:do-178c|DO-178C – Stack-Nachweis und Call-Graph-Verifikation]]