Was ist Rekursion?

Funktion, die sich selbst aufruft.

Wird verwendet, um Probleme zu lösen, die in Unterprobleme zerlegt werden können, die die gleiche Struktur wie das ursprüngliche Problem haben. Es muss eine Abbruchbedingung (Basisfall) vorhanden sein, um eine Endlosschleife zu vermeiden.

Beispiel für die Berechnung der Fakultät:

<?php
function factorial(int $n): int
{
    // Basisfall
    if ($n <= 1) {
        return 1;
    }
    // Rekursiver Aufruf
    return $n * factorial($n - 1);
}

echo factorial(5); // Gibt 120 aus
?>

Vorteile:

• Eleganz und Kürze des Codes für bestimmte Probleme.

Nachteile:

• Kann zu einem Stapelüberlauf führen bei zu tiefen Rekursionstiefen.
• Potenziell weniger effizient als iterative Lösungen für die gleichen Probleme aufgrund der zusätzlichen Kosten für Funktionsaufrufe.

Wird häufig verwendet, um Bäume zu durchlaufen, Dateisysteme zu durchsuchen, kombinatorische Probleme zu lösen.