Rekurencja

REKLAMA

Czysty kod. Podręcznik dobrego programisty
−40%41,40 zł
Algorytmy
69,00 zł

Rekurencja (inaczej rekursja) – odwołanie się funkcji lub definicji do samej siebie. Mówiąc inaczej, podejście rekurencyjne polega na tym, że rozwiązanie problemu wyraża się za pomocą rozwiązania tego samego problemu dla mniejszych danych wejściowych. Stosowanie rekurencji jest charakterystyczne dla algorytmów projektowanych metodą dziel i zwyciężaj.

Typowym problemem, dla którego można zastosować rekurencję, jest obliczanie silni. Przypomnijmy, że silnia z n jest zdefiniowana jako n!=1×2×…×n. Funkcja ta może być równoważnie zapisana jako:

n!=(n−1)!×n, dla n>0,
n!=1, dla n=0.

W powyższym przykładzie górny wiersz jest ogólnym równaniem rekurencji, zaś dolny wiersz jest wartością brzegową. W języku C++ powyższa funkcja byłaby zapisana w poniższy sposób.

int silnia(int n)
{
    if (n > 0)
    {
        return n * silnia(n-1);
    }
    else
    {
        return 1;
    }
};

Przekształcenie postaci rekurencyjnej funkcji do postaci zwartej (tzn. takiej, która nie zawiera odwołania do samej siebie) jest określane jako rozwiązanie rekurencji. Metody rozwiązywania rekurencji są dostępne między innymi w książkach podanych w bibliografii.

Algorytmy stosujące rekurencję są zazwyczaj proste w implementacji. Jednocześnie wiążą się one z pewnymi problemami. Przy podejściu rekurencyjnym ta sama funkcja jest wywoływana wielokrotnie, co zużywa pamięć operacyjną (w skrajnych przypadkach może to spowodować przepełnienie stosu).

Bibliografia

  • R.L. Graham, D.E. Knuth, O. Patashnik, Matematyka konkretna, Wydawnictwo Naukowe PWN , Warszawa, 2012, ISBN 9788301147648 [książka w księgarni Helion.pl].
  • Z.J. Czech, S. Deorowicz, P. Fabian, Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Gliwice, 2010, ISBN 9788373356689.
Ocena: +1 Tak Nie
Liczba głosów: 1.

Dodano: 2 maja 2020 17:21, ostatnia edycja: 2 maja 2020 17:21.

REKLAMA

Zobacz też

Quicksort, sortowanie szybkie – algorytm sortowania działający w średnim przypadku w czasie liniowo-logarytmicznym. Algorytm jest oparty na metodzie dziel i zwyciężaj. Nie jest to algorytm stabilny ani wykazujący zachowanie naturalne, jednak ze względu na efektywność jest algorytmem bardzo popularnym.

→ Czytaj całość

Algorytm Edmondsa-Karpa – algorytm wyszukiwania maksymalnego przepływu w sieci przepływowej. Jest to przypadek szczególny algorytmu Forda-Fulkersona.

W algorytmie Edmondsa-Karpa ścieżka powiększająca wyznaczana jest za pomocą przeszukiwania grafu wszerz. Dzięki temu w każdej iteracji algorytmu dołączana jest zawsze najkrótsza (pod względem liczby krawędzi) ścieżka powiększająca. W metodzie Forda-Fulkersona sposób wyznaczania ścieżki powiększającej jest dowolny.

→ Czytaj całość

Zanieczyszczenie Giniego (ang. Gini Impurity) – miara niejednorodności danego zbioru wyrażająca się wzorem:

$$G = ∑↙{n} p_n (1-p_n),$$

gdzie pn jest prawdopodobieństwem przynależności elementu do klasy n, czyli liczbą elementów danej klasy podzieloną przez liczbę elementów całego zbioru. Jeśli wszystkie elementy zbioru należą do tej samej klasy, zanieczyszczenie Giniego jest równe 0.

Zanieczyszczenia Giniego nie należy mylić ze współczynnikiem Giniego. Są to miary służące do wyrażania zupełnie innych rzeczy. Współczynnik Giniego określa nierównomierność rozkładu i jest wykorzystywany między innymi do liczbowego wyrażania nierówności w dochodach danego społeczeństwa.

→ Czytaj całość
Polityka prywatnościKontakt