Lab 4: Rekursion & Merge Sort

← Startseite

🧠 Worum geht es?

In Vorlesung 6 habt ihr Rekursion und den ersten O(n log n)-Sortierer Merge Sort kennengelernt. Heute setzt ihr beides selbst um — und seht den Quantensprung von O(n²) zu O(n log n) live.

Die Aufgaben bauen aufeinander auf: zuerst Rekursion verstehen (Fakultät, Fibonacci), dann Merge Sort schreiben, dann das Trace-Werkzeug üben. Wer schneller fertig ist, baut den Klassiker Tower of Hanoi (Bonus).

🌐 Programmiersprache — eure Wahl

Die Algorithmen sind sprachunabhängig. Implementiert sie in C (Standard), Python, Java, JavaScript, Rust, Arduino-C++ — was ihr am liebsten nutzt. Was zählt: der Algorithmus arbeitet korrekt und ihr versteht jeden Schritt.

Musterlösungen liegen nur in C vor. Wenn ihr in einer anderen Sprache arbeitet — übersetzt die Logik, die Syntax ändert sich, der Algorithmus nicht. Passwörter sind ganz unten frei zugänglich.

🎯 Lernziele

🌀 Rekursion

Funktionen, die sich selbst aufrufen — Basis-Fall + Verkleinerung — und der Call-Stack im Kopf nachvollziehen

🔀 Merge Sort

Aufteilen + Verschmelzen-Trick selbst implementieren — O(n log n) garantiert

🗺️ Rekursion in der Praxis

Klassiker wie Tower of Hanoi — wo Rekursion die Lösung elegant macht

📝 Trace-Werkzeug

Eine Rekursion auf Papier durchspielen — sehen, wie die Aufrufe runter und Werte hoch wandern

1 Rekursion verstehen — Fakultät ⏱️ 20 Min VL 6: Rekursion

Ziel: die einfachste Rekursion selbst schreiben — und den Call-Stack im Kopf nachvollziehen.

Definition:

n! = 1 · 2 · 3 · … · n. Rekursiv: n! = n · (n-1)!, mit 1! = 1 als Basis-Fall.

Aufgabe:

Schreibe eine rekursive Funktion fakt(n), die n! berechnet.
Teste mit n = 1, 5, 10. Erwartete Werte: 1, 120, 3 628 800.
Auf Papier: trace den Call-Stack für fakt(4) — push-Phase, dann Rückgabe-Phase mit den Multiplikationen.

Pseudocode:

function fakt(n): if n <= 1: return 1 return n * fakt(n - 1)

💡 Hinweis: bei n > 12 läuft int über (12! = 479 001 600 passt gerade, 13! nicht mehr). Nimm long long für größere Werte — oder bleib bis n=12, das ist für die Übung sowieso ausreichend.

🤔 Denkfrage: was passiert ohne den Basis-Fall (if n <= 1 return 1)? Probier's aus — und sei bereit, das Programm mit Ctrl+C abzubrechen.

🔒 Musterlösung in C

Falsches Passwort!

#include <stdio.h>

long long fakt(int n) {
    if (n <= 1) {
        return 1;                  // Basis-Fall
    }
    return (long long)n * fakt(n - 1);   // rekursiver Schritt
}

int main(void) {
    for (int n = 1; n <= 10; n++) {
        printf("%2d! = %lld\n", n, fakt(n));
    }
    return 0;
}

Erwartete Ausgabe:

 1! = 1
 2! = 2
 3! = 6
 4! = 24
 5! = 120
 ...
10! = 3628800

2 Fibonacci — Rekursion vs. Iteration (Komplexität spüren) ⏱️ 25 Min VL 6 + VL 5

Ziel: ein Algorithmus, zwei Implementierungen — und sehen, warum die naive Rekursion bei großen n unbenutzbar ist.

Definition:

fib(0) = 0, fib(1) = 1, fib(n) = fib(n-1) + fib(n-2).

Aufgabe:

Implementiere naive Rekursion: fib_rek(n) ruft sich zweimal selbst auf.
Implementiere Iteration: fib_iter(n) mit einer for-Schleife und zwei Variablen.
Miss die Laufzeit beider für n = 10, 20, 30, 35, 40 mit clock() aus <time.h>.

Erwartete Beobachtung:

Die iterative Version ist instant — auch bei n = 1000. Die rekursive Version explodiert nach n = 40: jeder Schritt mehr verdoppelt die Zeit. Warum?

⚠️ Warnung: startet NICHT mit fib_rek(50) — das dauert Minuten. Geht schrittweise hoch.

🤔 Komplexitäts-Analyse: Die naive Rekursion hat O(2ⁿ) Aufrufe — jeder Knoten im Rekursions-Baum verzweigt sich in zwei. Die iterative Version ist O(n). Bei n = 40 ist das der Unterschied zwischen einer Sekunde und einer Stunde.

Bonus-Frage: könntest du die rekursive Version mit Memoization (Zwischenergebnisse in einem Array merken) auf O(n) bringen? Spoiler: ja — aber das wartet bis VL 12.

🔒 Musterlösung in C

Falsches Passwort!

#include <stdio.h>
#include <time.h>

// Naive Rekursion — O(2^n)
long long fib_rek(int n) {
    if (n < 2) return n;
    return fib_rek(n - 1) + fib_rek(n - 2);
}

// Iteration — O(n)
long long fib_iter(int n) {
    if (n < 2) return n;
    long long a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

void messung(int n) {
    clock_t start, ende;
    double ms;
    long long ergebnis;

    start = clock();
    ergebnis = fib_iter(n);
    ende = clock();
    ms = (double)(ende - start) / CLOCKS_PER_SEC * 1000.0;
    printf("n=%2d  iter: %lld  (%.3f ms)\n", n, ergebnis, ms);

    start = clock();
    ergebnis = fib_rek(n);
    ende = clock();
    ms = (double)(ende - start) / CLOCKS_PER_SEC * 1000.0;
    printf("       rek:  %lld  (%.3f ms)\n", ergebnis, ms);
    printf("\n");
}

int main(void) {
    int werte[] = {10, 20, 30, 35, 40};
    for (int i = 0; i < 5; i++) {
        messung(werte[i]);
    }
    return 0;
}

Beobachtung (typisch):

n=10  iter:    55  (0.000 ms)
       rek:    55  (0.001 ms)

n=30  iter: 832040 (0.000 ms)
       rek: 832040 (3.4 ms)

n=40  iter: 102334155 (0.000 ms)
       rek: 102334155 (420 ms)   ← 100 000× langsamer!

3 Merge Sort selbst bauen ⏱️ 30 Min VL 6: Merge Sort

Ziel: den ersten O(n log n)-Sortierer von Hand implementieren — und live sehen, wie viel schneller er als Bubble Sort ist.

Aufgabe:

Implementiere die Hilfsfunktion merge(a, l, m, r) — verschmilzt zwei sortierte Teile a[l..m] und a[m+1..r] in einen sortierten Teil.
Implementiere merge_sort(a, l, r) — Basis-Fall: l >= r. Sonst: linke Hälfte rekursiv sortieren, rechte rekursiv, dann verschmelzen.
Teste mit [5, 2, 8, 1, 9, 3, 7, 4] → erwartet: [1, 2, 3, 4, 5, 7, 8, 9].
Teste auch mit bereits sortiertem und umgekehrt sortiertem Array — Merge Sort ist immer O(n log n), unabhängig vom Input.

Pseudocode (aus VL 6):

function mergeSort(a, l, r): if l >= r: return // Basis m = (l + r) / 2 mergeSort(a, l, m) // linke Hälfte mergeSort(a, m + 1, r) // rechte Hälfte merge(a, l, m, r) // hier wird sortiert function merge(a, l, m, r): Hilfs-Array hilfs anlegen i = l, j = m + 1, k = 0 while beide Hälften noch Karten haben: kleinere von beiden in hilfs[k] Zeiger weiterrücken Rest aus nicht-leerer Hälfte übernehmen hilfs zurück nach a[l..r] kopieren

💡 Tipp: nutzt ein statisches Hilfs-Array (int hilfs[1024];) für die ersten Tests. Für richtige Skalierung könnt ihr später auf malloc umsteigen — aber für n ≤ 1024 reicht statisch.

🔒 Musterlösung in C

Falsches Passwort!

#include <stdio.h>

void merge(int a[], int l, int m, int r) {
    int hilfs[1024];
    int i = l, j = m + 1, k = 0;

    while (i <= m && j <= r) {
        if (a[i] <= a[j]) { hilfs[k++] = a[i++]; }
        else              { hilfs[k++] = a[j++]; }
    }
    while (i <= m) hilfs[k++] = a[i++];
    while (j <= r) hilfs[k++] = a[j++];

    for (int x = 0; x < k; x++) {
        a[l + x] = hilfs[x];
    }
}

void merge_sort(int a[], int l, int r) {
    if (l >= r) return;
    int m = (l + r) / 2;
    merge_sort(a, l, m);
    merge_sort(a, m + 1, r);
    merge(a, l, m, r);
}

void drucke(int a[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
}

int main(void) {
    int a[] = {5, 2, 8, 1, 9, 3, 7, 4};
    int n = 8;

    printf("vorher:  ");  drucke(a, n);
    merge_sort(a, 0, n - 1);
    printf("nachher: ");  drucke(a, n);

    return 0;
}

Erwartete Ausgabe:

vorher:  5 2 8 1 9 3 7 4
nachher: 1 2 3 4 5 7 8 9

4 Rekursives Maximum im Array ⏱️ 20 Min VL 6: Rekursion auf Arrays

Ziel: ein iteratives Problem rekursiv lösen — und sehen, wie elegant der Code wird.

Die Idee:

Das Maximum eines Arrays a[0..n-1] ist entweder das letzte Element a[n-1], oder das Maximum aus dem Rest a[0..n-2]. Das ist eine rekursive Definition — daher die natürliche Lösung.

Aufgabe:

Schreibe eine rekursive Funktion max_rek(int a[], int n).
Basis-Fall: bei n == 1 ist a[0] das Maximum.
Rekursiver Schritt: vergleiche a[n-1] mit dem Maximum des Rests (rekursiver Aufruf mit n-1).
Teste mit [3, 9, 1, 7, 5, 8, 2] → erwartet: 9.

Pseudocode:

function max_rek(a, n): if n == 1: return a[0] // Basis-Fall rest_max = max_rek(a, n - 1) // Maximum von a[0..n-2] if a[n-1] > rest_max: return a[n-1] return rest_max

💡 Was ist ein Trace — und wie liest man einen?

Ein Trace (deutsch: Spurführung) ist ein Papier-Durchspielen der Rekursion — Schritt für Schritt, ohne den Computer. Das ist das Werkzeug, um Rekursion zu verstehen: man sieht die Aufrufe runtergehen und die Werte hochkommen.

So liest man einen Trace:

Obere Hälfte (Pfeile →): der Aufruf „geht runter" — jede Zeile ist ein neuer rekursiver Aufruf mit kleinerem Problem. Man trackt mit Einrückung, wie tief wir sind.
Unten — die Basis: die innerste Zeile gibt zum ersten Mal einen konkreten Wert zurück (kein rekursiver Aufruf mehr).
Untere Hälfte (Pfeile ←): die Aufrufe „klappen wieder auf" — jeder Eltern-Aufruf bekommt jetzt den zurückgegebenen Wert und kann seine eigene Rechnung fertigstellen.

Beispiel-Trace für a = [3, 9, 1, 7]:

max_rek([3,9,1,7], 4) → max(7, max_rek(..., 3))    // will Maximum von 7 und vom Rest
max_rek([3,9,1], 3)   → max(1, max_rek(..., 2))    // will Maximum von 1 und vom Rest
max_rek([3,9], 2)     → max(9, max_rek(..., 1))    // will Maximum von 9 und vom Rest
max_rek([3], 1)       → 3                          // BASIS — gibt 3 zurück
              ← 9 (= max(9, 3))                    // jetzt max(9, 3) berechnen → 9
       ← 9 (= max(1, 9))                           // max(1, 9) → 9
       ← 9 (= max(7, 9))                           // max(7, 9) → 9 ← Endergebnis

So baut ihr selbst einen Trace:

Nehmt ein leeres Blatt Papier.
Schreibt links den ersten Aufruf hin (z.B. max_rek([3,9,1,7], 4)).
Schaut den Code an: was passiert? Wenn ein rekursiver Aufruf kommt, schreibt ihn eingerückt in die nächste Zeile und merkt euch, „was nach diesem Aufruf noch zu tun ist" (rechts daneben).
Macht so weiter, bis der Basis-Fall greift. Schreibt den konkreten Rückgabewert hin.
Geht jetzt rückwärts nach oben: für jede Zeile setzt ihr den Rückgabewert von unten ein und führt die offene Rechnung aus.

Übung: macht denselben Trace für a = [5, 1, 8, 2] auf Papier. Vergleicht zum Schluss mit eurem Code-Output.

🤔 Vergleich: die iterative Version dieser Aufgabe ist eine simple for-Schleife (Lab 3 Niveau). Die rekursive ist konzeptuell schöner — und übt das „kleineres Problem desselben Typs"-Denken, das ihr für Merge Sort und Quicksort braucht.

Komplexität: beide Versionen sind O(n) — Rekursion bringt hier keinen Speed-Vorteil, sondern dient als Denkschule.

🔒 Musterlösung in C

Falsches Passwort!

#include <stdio.h>

int max_rek(int a[], int n) {
    if (n == 1) {
        return a[0];                  // Basis-Fall
    }
    int rest_max = max_rek(a, n - 1); // Maximum aus a[0..n-2]
    if (a[n - 1] > rest_max) {
        return a[n - 1];
    }
    return rest_max;
}

int main(void) {
    int a[] = {3, 9, 1, 7, 5, 8, 2};
    int n = 7;

    printf("Maximum: %d\n", max_rek(a, n));   // → 9
    return 0;
}

Variante (kompakter mit Ternary-Operator):

int max_rek(int a[], int n) {
    if (n == 1) return a[0];
    int rest = max_rek(a, n - 1);
    return (a[n - 1] > rest) ? a[n - 1] : rest;
}

5 Tower of Hanoi — Rekursion in der Praxis ⏱️ 25 Min · BONUS VL 6: Rekursion

Ziel: ein Klassiker — und der beste Beweis, wie elegant Rekursion sein kann. Gleiche Lösung in einer Schleife wäre richtig hässlich.

Das Problem:

Drei Stäbe (A, B, C). Auf A stehen n Scheiben — größte unten, kleinste oben. Ziel: alle Scheiben auf C bringen. Regeln:

nur eine Scheibe pro Zug
eine größere Scheibe darf nie auf eine kleinere

Die rekursive Idee:

Um n Scheiben von A nach C zu bewegen (mit B als Zwischen-Stab):

Verschiebe n-1 Scheiben von A nach B (mit C als Zwischen)
Verschiebe die unterste Scheibe von A nach C (ein Zug)
Verschiebe n-1 Scheiben von B nach C (mit A als Zwischen)

Aufgabe:

Implementiere hanoi(n, von, nach, ueber).
Drucke jeden Zug (z.B. "Scheibe 1: A -> C").
Teste mit n = 3, 4, 5. Erwartete Zug-Anzahl: 2ⁿ - 1.

Pseudocode:

function hanoi(n, von, nach, ueber): if n == 1: drucke "Scheibe 1: von -> nach" return hanoi(n - 1, von, ueber, nach) // n-1 Scheiben aus dem Weg drucke "Scheibe n: von -> nach" // unterste verschieben hanoi(n - 1, ueber, nach, von) // n-1 Scheiben drauf

🤔 Komplexität: T(n) = 2 · T(n-1) + 1 = 2ⁿ - 1 Züge.
Für n = 64 (klassisches „Türme von Hanoi"-Rätsel der Mönche): 18 446 744 073 709 551 615 Züge. Bei 1 Zug/Sekunde → 580 Mrd. Jahre. Daher der Mythos „bis das Universum endet".

🔒 Musterlösung in C

Falsches Passwort!

#include <stdio.h>

int zaehler = 0;

void hanoi(int n, char von, char nach, char ueber) {
    if (n == 1) {
        printf("  Scheibe 1: %c -> %c\n", von, nach);
        zaehler++;
        return;
    }
    hanoi(n - 1, von, ueber, nach);             // n-1 aus dem Weg
    printf("  Scheibe %d: %c -> %c\n", n, von, nach);
    zaehler++;
    hanoi(n - 1, ueber, nach, von);             // n-1 drauf
}

int main(void) {
    int n = 4;
    printf("Hanoi mit %d Scheiben:\n", n);
    hanoi(n, 'A', 'C', 'B');
    printf("\nGesamt: %d Züge  (2^%d - 1 = %d)\n",
           zaehler, n, (1 << n) - 1);
    return 0;
}

Erwartete Ausgabe (n=4):

Hanoi mit 4 Scheiben:
  Scheibe 1: A -> B
  Scheibe 2: A -> C
  Scheibe 1: B -> C
  Scheibe 3: A -> B
  Scheibe 1: C -> A
  Scheibe 2: C -> B
  Scheibe 1: A -> B
  Scheibe 4: A -> C
  Scheibe 1: B -> C
  Scheibe 2: B -> A
  Scheibe 1: C -> A
  Scheibe 3: B -> C
  Scheibe 1: A -> B
  Scheibe 2: A -> C
  Scheibe 1: B -> C

Gesamt: 15 Züge  (2^4 - 1 = 15)

✅ Was du nach diesem Lab können solltest

☐ Rekursive Funktionen mit Basis-Fall und Verkleinerung selbständig schreiben
☐ Den Call-Stack im Kopf für einfache Rekursionen nachvollziehen
☐ Merge Sort von Grund auf implementieren — sowohl merge() als auch merge_sort()
☐ Iterative Probleme rekursiv ausdrücken (Maximum, Tower of Hanoi)
☐ Einen Trace (Spurführung) auf Papier selbst aufbauen und lesen

🎯 Reflexion am Ende

Welche Aufgabe war die schwierigste — und woran lag's? (Algorithmus-Verständnis? Pointer? Rekursion?)
Hast du eine Endlos-Rekursion produziert (vergessener Basis-Fall)? Wie hat sich der Stack-Overflow bemerkbar gemacht?
Wie viel fühlbar schneller war Merge/Quick gegenüber Bubble bei n = 10 000?
Wenn du nicht in C programmiert hast — was war einfacher in deiner Sprache, was schwerer?

🔑 Passwörter für die Musterlösungen

Die Passwörter stehen unten — frei zugänglich. Bitte fair spielen: erst selbst implementieren, dann mit der Musterlösung vergleichen. Eine Lösung, die ihr nur abgeschrieben habt, hilft euch in der Klausur nicht.

Aufgabe	Thema	Passwort
Aufgabe 1	Rekursion — Fakultät	`fakultaet`
Aufgabe 2	Fibonacci — Rekursion vs. Iteration	`fibonacci`
Aufgabe 3	Merge Sort	`merge`
Aufgabe 4	Rekursives Maximum + Trace-Tutorial	`maximum`
Aufgabe 5	Tower of Hanoi (Bonus)	`hanoi`

Hinweis für Python/Java/Rust-Lösungen: die Algorithmen sind 1:1 übertragbar — übersetzt nur die Syntax. Eigene Musterlösungen für jede Sprache gibt es nicht.

← Startseite

🧠 Worum geht es?

🌐 Programmiersprache — eure Wahl

🎯 Lernziele

🌀 Rekursion

🔀 Merge Sort

🗺️ Rekursion in der Praxis

📝 Trace-Werkzeug

1 Rekursion verstehen — Fakultät ⏱️ 20 Min VL 6: Rekursion

Definition:

Aufgabe:

Pseudocode:

2 Fibonacci — Rekursion vs. Iteration (Komplexität spüren) ⏱️ 25 Min VL 6 + VL 5

Definition:

Aufgabe:

Erwartete Beobachtung:

3 Merge Sort selbst bauen ⏱️ 30 Min VL 6: Merge Sort

Aufgabe:

Pseudocode (aus VL 6):

4 Rekursives Maximum im Array ⏱️ 20 Min VL 6: Rekursion auf Arrays

Die Idee:

Aufgabe:

Pseudocode:

5 Tower of Hanoi — Rekursion in der Praxis ⏱️ 25 Min · BONUS VL 6: Rekursion

Das Problem:

Die rekursive Idee:

Aufgabe:

Pseudocode:

✅ Was du nach diesem Lab können solltest

🎯 Reflexion am Ende

🔑 Passwörter für die Musterlösungen

🚀 Rekursion + O(n log n) — beherrscht