Rekurencja

Słownik kwalifikacji INF.03 - Tworzenie i administrowanie stronami i aplikacjami internetowymi oraz bazami danych

Co to jest rekurencja?

Rekurencja to technika programowania, w której funkcja wywołuje samą siebie. Jest używana do rozwiązywania problemów, które można podzielić na mniejsze, podobne podproblemy.

Najważniejsze elementy rekurencji:
- warunek zakończenia — określa, kiedy funkcja ma przestać wywoływać samą siebie,
- wywołanie rekurencyjne — ponowne wywołanie tej samej funkcji dla prostszego przypadku.

Bez warunku zakończenia funkcja będzie wywoływać się bez końca, co może doprowadzić do błędu przepełnienia stosu.

Przykład w PHP

function silnia($n) {
    if ($n <= 1) {
        return 1; // warunek zakończenia
    }

    return $n * silnia($n - 1); // wywołanie rekurencyjne
}

echo silnia(5); // 120

W tym przykładzie funkcja silnia() wywołuje samą siebie, aż argument $n osiągnie wartość 1.

Rekurencja a iteracja

Iteracja polega na wielokrotnym wykonywaniu instrukcji, np. za pomocą pętli for, while lub foreach. Rekurencja zamiast pętli wykorzystuje kolejne wywołania funkcji.

Oba podejścia mogą często rozwiązać ten sam problem, ale rekurencja jest szczególnie wygodna przy strukturach drzewiastych, np. menu wielopoziomowym, katalogach lub komentarzach z odpowiedziami.

Typowe zastosowania

  • obliczanie silni,
  • przeszukiwanie drzewa kategorii,
  • generowanie zagnieżdżonych menu,
  • przetwarzanie struktur katalogów,
  • algorytmy typu quicksort lub merge sort.

W pytaniu egzaminacyjnym poprawna odpowiedź to: funkcja wywołująca samą siebie to rekurencja.