Rekurencja

Co to jest rekurencja?

Rekurencja to technika programowania, w której funkcja wywołuje samą siebie. Takie rozwiązanie stosuje się wtedy, gdy problem można podzielić na mniejsze problemy tego samego typu.

Najważniejszy warunek: funkcja rekurencyjna musi mieć warunek zakończenia, czyli przypadek bazowy. Bez niego funkcja będzie wywoływać się w nieskończoność, aż do przepełnienia stosu wywołań.

Przykład rekurencji

int fn(int a) {
    if (a == 1) return 1;      // przypadek bazowy
    return fn(a - 1) + 2;      // wywołanie tej samej funkcji
}

W tym przykładzie funkcja fn wywołuje samą siebie w instrukcji:

fn(a - 1)

Dlatego jest to rekurencja.

Elementy funkcji rekurencyjnej

• Przypadek bazowy - warunek kończący rekurencję, np. if (a == 1) return 1;
• Wywołanie rekurencyjne - funkcja wywołuje samą siebie, np. fn(a - 1)
• Zmiana argumentu - argument powinien zbliżać się do przypadku bazowego, np. a - 1

Co nie jest rekurencją?

Nie wystarczy, że funkcja coś oblicza lub zwraca wynik. Rekurencja występuje tylko wtedy, gdy funkcja wywołuje samą siebie.

Przykład bez rekurencji:

int fn(int a) {
    if (a == 1) return 1;
    return (a - 1) + 2;
}

Tutaj nie ma wywołania fn(...), więc nie jest to rekurencja.

Typowe zastosowania

Rekurencję stosuje się m.in. przy:

• obliczaniu silni,
• przeszukiwaniu drzew,
• algorytmach typu dziel i zwyciężaj,
• sortowaniu szybkim,
• rozwiązywaniu problemów matematycznych.