Rekursion

Rekursion ist eine Programmiertechnik, bei der eine Funktion sich während ihrer Definition oder Ausführung direkt oder indirekt selbst aufruft. Die Kernidee besteht darin, ein komplexes Problem in kleinere Teilprobleme derselben Struktur zu zerlegen.

Grundlegende Konzepte der Rekursion

Änderungen der Stack-Frames bei rekursiven Aufrufen – am Beispiel factorial(3)

fact(3)Warten auf die Rückkehr von fact(2) → Push auf den Stack

↓ Aufruf

fact(2)Warten auf die Rückkehr von fact(1) → Push auf den Stack

↓ Aufruf

fact(1)Warten auf die Rückkehr von fact(0) → Push auf den Stack

↓ Aufruf

fact(0) = 1Basisfall! Rückgabe beginnt → Pop vom Stack

↑ Ebene für Ebene zurückgeben (LIFO)

fact(3) = 3 × fact(2) = 3 × 2 × fact(1) = 3 × 2 × 1 × fact(0) = 3 × 2 × 1 × 1 = 6

Orangefarbene Box (Basisbedingung) → Rekursion stoppen und mit der Rückgabe beginnen | Stack-Frames werden in LIFO-Reihenfolge entfernt: Der zuletzt Hinzugefügte kehrt zuerst zurück

Eine gültige rekursive Funktion muss zwei Schlüsselelemente enthalten:

Element	Bedeutung	Beispiel (Fakultät)
Basisbedingung	Die Bedingung zum Beenden der Rekursion, die eine Endlosrekursion verhindert.	`if (n == 0) return 1;`
Rekursionsbedingung	Das Problem in kleinere Teilprobleme zerlegen und sich selbst aufrufen.	`return n * factorial(n-1);`

Klassische Rekursionsprobleme

Fakultät

Beispiel

#include <stdio.h>

/* Rekursive Fakultätsimplementierung
n! = n × (n-1)!, Basisbedingung: 0! = 1 */
long long factorial(int n) {
if (n == 0) return 1; /* Basisfall */
return n * factorial(n - 1); /* Rekursionsfall */
}

int main() {
printf("5! = %lld\n", factorial(5)); /* Ausgabe: 120 */
return 0;
}

Fibonacci-Folge

Beispiel

#include <stdio.h>

/* Naive Rekursion: viele wiederholte Berechnungen, O(2ⁿ) */
int fib(int n) {
if (n <= 1) return n; /* Basisfall */
return fib(n-1) + fib(n-2); /* Rekursionsfall */
}

/* Memoization-Optimierung: berechnete Ergebnisse zwischenspeichern, O(n) */
#define MAX 100
long long memo[MAX] = {0};

long long fibMemo(int n) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n]; /* Bereits berechnet, direkt zurückgeben */
memo[n] = fibMemo(n-1) + fibMemo(n-2);
return memo[n];
}

int main() {
printf("fib(10) (naiv): %d\n", fib(10)); /* Ausgabe: 55 */
printf("fibMemo(50) (memoisiert): %lld\n", fibMemo(50)); /* Ausgabe: 12586269025 */
return 0;
}

Problem der Türme von Hanoi

Beispiel

#include <stdio.h>

/* Rekursive Lösung der Türme von Hanoi
Bewege n Scheiben von src nach dst mit Hilfe von aux
Schritte: Bewege n-1 von src→aux, die größte Scheibe von src→dst, n-1 von aux→dst */
void hanoi(int n, char src, char aux, char dst) {
if (n == 1) {
printf("Bewege Scheibe 1 von %c nach %c\n", src, dst);
return;
}
hanoi(n - 1, src, dst, aux); /* Verschiebe n-1 Scheiben von src nach aux */
printf("Verschiebe Scheibe %d von %c nach %c\n", n, src, dst);
hanoi(n - 1, aux, src, dst); /* Verschiebe n-1 Scheiben von aux nach dst */
}

int main() {
printf("Türme von Hanoi (3 Scheiben):\n");
hanoi(3, 'A', 'B', 'C');
/* Ausgabe: 7 Schritte insgesamt (2³-1), minimale Schritte = 2ⁿ-1 */
return 0;
}

Rekursion vs. Iteration

Dimension	Rekursion	Iteration
Lesbarkeit des Codes	Hoch(Nahe an der mathematischen Definition)	Manchmal nicht so intuitiv wie Rekursion
Ausführungseffizienz	Geringerer(Stackframe-Overhead)	Höher
Speicher-Overhead	O(Rekursionstiefe) Stack-Speicher	O(1)
Stacküberlauf-Risiko	Ja(Wenn die Tiefe zu groß ist)	Keine
Anwendbare Strukturen	Natürliche rekursive Strukturen wie Bäume und Graphen	Lineare Strukturen wie Arrays

EndrekursionSie ist eine spezielle Form der Rekursion, bei der der rekursive Aufruf die letzte im Funktionskörper ausgeführte Operation ist. Einige Compiler können Endrekursion optimieren, indem sie sie in eine äquivalente Iteration umwandeln, um Stack-Speicher zu sparen. Allerdings aktivieren nicht alle C-Compiler diese Optimierung standardmäßig.

Weitere Erweiterungen