Rekursion ist eine Funktion, die sich selbst aufruft — mit einem kleineren Problem. Klingt verrückt, ist aber das Werkzeug, mit dem wir Bäume traversieren, Sortieralgorithmen schreiben, Labyrinthe lösen und Sprachen parsen.
Klassisches Beispiel — Fakultät:
function fact(n) {
if (n <= 1) return 1; // Basisfall
return n * fact(n - 1); // Rekursionsfall
}
fact(5) = 5 * fact(4)
= 5 * 4 * fact(3)
= 5 * 4 * 3 * fact(2)
= 5 * 4 * 3 * 2 * fact(1)
= 5 * 4 * 3 * 2 * 1 = 120Faustregel: „Eine Rekursion ohne Basisfall ist eine Endlosschleife mit Etiketten."
Zurück zu Informatik