Czym jest rekurencja?

Funkcja wywołująca samą siebie.

Stosowana do rozwiązywania problemów, które można podzielić na podproblemy o takiej samej strukturze jak problem główny. Musi mieć warunek zakończenia (przypadek bazowy), aby uniknąć nieskończonej pętli.

Przykład obliczania silni:

<?php
function factorial(int $n): int
{
    // Przypadek bazowy
    if ($n <= 1) {
        return 1;
    }
    // Wywołanie rekurencyjne
    return $n * factorial($n - 1);
}

echo factorial(5); // Wypisze 120
?>

Zalety:

• Elegancja i zwięzłość kodu dla niektórych problemów.

Wady:

• Może prowadzić do przepełnienia stosu przy zbyt głębokim poziomie rekurencji.
• Potencjalnie mniej wydajna niż rozwiązania iteracyjne dla tych samych problemów z powodu narzutów związanych z wywołaniami funkcji.

Często stosowana do przechodzenia przez drzewa, systemy plików, rozwiązywania problemów kombinatorycznych.