algorytm.org

Rekurencja

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Rekurencja
Ocena użytkowników:***** / 146
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 01 sierpnia 2005 22:26

Charakterystyczną cechą funkcji (procedury) rekurencyjnej jest to, że wywołuje ona samą siebie. Drugą cechą rekursji jest jej dziedzina, którą mogą być tylko liczby naturalne.
Najłatwiej zrozumieć mechanizm działania rekursji na przykładzie silni: rekurencyjny wzór na obliczenie n! zapisuje się w ten sposób: n!=n*(n-1)!
Ze wzoru tego wynika, że aby obliczyć np. 4!, należy najpierw obliczyć 3!. Ale żeby obliczyć 3! trzeba obliczyć 2! itd. aż dojdziemy do 0!, które jak wiemy wynosi 1.
Sposób obliczenia 4! wygląda więc następująco:
4!=4*3!=4*3*2!=4*3*2*1!=4*3*2*1*0!=4*3*2*1*1=24
Przykładowa implementacja funkcji rekurencyjnej obliczającej n! wygląda tak:

function silnia(n:integer):integer;
begin
if (n=0)or(n=1) then silnia:=1 else
silnia:=n*silnia(n-1);
end;

Inny przykład zastosowania rekursji to Ciąg Fibonacciego.
Pojawia się pytanie, czy warto stosować rekursję? Odpowiedz nie jest jednoznaczna. Funkcje rekurencyjne mają dużą złożoność obliczeniową a ponad to wymagają zastosowania wewnętrznego stosu. Należy więc ich unikać. Niestety zlikwidowanie rekursji jest czasami bardzo trudne i wymaga sporych umiejętności. Są jednak przypadki, w których likwidacja rekursji jest możliwa i prosta, na przykład omawiana przez nas silnia daje się przedstawić w postaci iteracji (zob. Silnia).

Poprawiony: 15 sierpnia 2005 23:52
Komentarze
photo
+117 # sznurkownia.pl 2009-09-03 23:48
żeby zrozumieć rekurencje, trzeba najpierw zrozumieć rekurencję.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # pirx 2010-01-31 15:10
bardzo fajna strona i ciekawe przykłady
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-8 # PLUDi 2010-02-23 12:59
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # kamikadze 2010-05-04 20:24
Krótko i na temat
i o to chodzi
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+2 # kleer94 2011-06-20 01:11
Co do pytania postawionego na koniec to rekurencja jest w sumie zawsze stosowana w przeszukiwaniu katalogów.
W sumie nie ma lepszej metody o ile w ogóle jeszcze jakaś istnieje.
Załóżmy, że chcemy wypisać wszystkie nazwy plików, na dysku C. Sprawdza się wtedy każdy plik po kolei i wypisuje jego zawartość. Jeśli napotykamy na katalog to stosujemy na nim rekurencję naszej funkcji i tak oto mamy wydrukowane wszystkie nazwy plików na calutkim dysku.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz