Unit 20 – Rekursion – Grundidee und einfache Beispiele

Ömer sagt:

Rekursion ist wie Matrjoschka-Puppen: Eine Funktion, die sich selbst aufruft – aber mit einem kleineren Problem. Das klingt verrückt, ist aber ein elegantes Konzept! Das Wichtigste: Es muss einen Basisfall geben, sonst läuft es ewig! 🪆

Was ist Rekursion? Basisfall (Base Case) Rekursionsfall Fakultät rekursiv Fibonacci-Zahlen

🪆 Was ist Rekursion?

Eine rekursive Funktion ruft sich selbst auf – aber mit einem kleineren oder vereinfachten Problem. Sie muss zwei Teile haben:

1. Basisfall (Base Case)

Die Bedingung, bei der die Funktion aufhört sich selbst aufzurufen. Ohne Basisfall: Endlosrekursion!

Beispiel: Fakultät(0) = 1 → stop!

2. Rekursionsfall

Die Funktion ruft sich selbst auf, aber mit einem kleineren Argument. Das Problem wird kleiner bis zum Basisfall.

Beispiel: Fakultät(n) = n × Fakultät(n-1)

💻 Klassiker: Fakultät

Die Fakultät von n (geschrieben n!) ist: n! = n × (n-1) × (n-2) × ... × 1. Also: 5! = 5 × 4 × 3 × 2 × 1 = 120

fakultaet.cC

#include <stdio.h>

int fakultaet(int n) {
    if (n == 0) return 1;      // Basisfall: 0! = 1
    return n * fakultaet(n-1);  // Rekursionsfall
}

int main() {
    printf("5! = %d\n", fakultaet(5));  // 120
    printf("3! = %d\n", fakultaet(3));  // 6
    return 0;
}

Aufrufkette: fakultaet(4)

fakultaet(4) → 4 × fakultaet(3)

fakultaet(3) → 3 × fakultaet(2)

fakultaet(2) → 2 × fakultaet(1)

fakultaet(1) → 1 × fakultaet(0)

fakultaet(0) → 1 ← Basisfall!

→ 1 × 1 = 1

→ 2 × 1 = 2

→ 3 × 2 = 6

→ 4 × 6 = 24

💻 Fibonacci-Zahlen

Die Fibonacci-Folge: 0, 1, 1, 2, 3, 5, 8, 13... Jede Zahl ist die Summe der zwei vorherigen:

fibonacci.cC

int fibonacci(int n) {
    if (n <= 1) return n;    // Basisfall: fib(0)=0, fib(1)=1
    return fibonacci(n-1) + fibonacci(n-2);
}

int main() {
    for (int i = 0; i < 8; i++)
        printf("%d ", fibonacci(i));
}

▶ Ausgabe

0 1 1 2 3 5 8 13

✏️ Übungen

Übung 1

Basisfall und Rekursionsfall finden

Beschreibe Basisfall und Rekursionsfall für die Funktion summe(n) die 1+2+...+n berechnet:

Basisfall (wann stoppt die Rekursion?):

Rekursionsfall:

summe(n) = n + summe(n-1), und summe(0) = 0

Übung 2

Aufrufkette zeichnen

Zeichne die Aufrufkette für fakultaet(3) und zeige alle Zwischenschritte:

Übung 3 – Programm

Rekursive Summe

Schreibe eine rekursive Funktion summe(int n), die 1 + 2 + 3 + ... + n berechnet:

#include <stdio.h> int summe(int n) { if (___) return 0; // Basisfall return ___; // Rekursionsfall } int main() { printf("Summe 1-5: %d\n", summe(5)); // 15 printf("Summe 1-10: %d\n", summe(10)); // 55 return 0; }

summe(5) = 5 + summe(4) = 5 + 4 + summe(3) = ... = 5+4+3+2+1+0 = 15

Übung 4 – Kapitel-Abschluss

Potenz rekursiv

Schreibe eine rekursive Funktion potenz(int basis, int exp), die basis^exp berechnet. (Basisfall: exp == 0 → 1. Rekursionsfall: basis × potenz(basis, exp-1))

#include <stdio.h> int potenz(int basis, int exp) { /* Basisfall und Rekursionsfall */ } int main() { printf("2^8 = %d\n", potenz(2, 8)); // 256 printf("3^4 = %d\n", potenz(3, 4)); // 81 return 0; }

Übung 5 – Bonus

Fibonacci: iterativ vs. rekursiv

Schreibe Fibonacci sowohl rekursiv als auch iterativ und vergleiche die Ergebnisse. Bei großen Zahlen ist die iterative Version viel schneller – erkläre warum:

#include <stdio.h> /* Rekursiv – elegant aber langsam */ int fib_rekursiv(int n) { if (n <= 1) return n; return fib_rekursiv(n - 1) + fib_rekursiv(n - 2); } /* Iterativ – schnell und effizient */ int fib_iterativ(int n) { if (n <= 1) return n; int a = 0, b = 1, c; for (int i = 2; i <= n; i++) { c = a + b; a = b; b = c; } return b; } int main() { for (int i = 0; i <= 10; i++) { printf("fib(%2d): rekursiv=%d iterativ=%d\n", i, fib_rekursiv(i), fib_iterativ(i)); } return 0; }

fib_rekursiv(40) berechnet dieselben Werte millionenfach neu! fib_iterativ(40) braucht nur 40 Schritte. Das ist der Unterschied zwischen O(2^n) und O(n).