Autor artykułu: mgr Jerzy Wałaszek
©2014 mgr
Jerzy Wałaszek
I LO w Tarnowie
|
Autor artykułu: mgr Jerzy Wałaszek |
©2014 mgr
Jerzy Wałaszek
|
|
Słowo rekurencja (również rekursja) wywodzi się z języka łacińskiego - recurrere = biec z powrotem. W algorytmice mówimy, że dany algorytm jest rekurencyjny, jeśli do rozwiązania pewnego problemu wykorzystuje on sam siebie. W programowaniu dana funkcja jest rekurencyjna, jeśli wywołuje samą siebie. Kolejne wywołania takiej funkcji nazywamy rekurencyjnym ciągiem wywołań. Ciąg ten nie może być nieskończony - każde wywołanie funkcji powoduje umieszczenie w pamięci komputera adresu powrotu, czyli miejsca w programie, do którego wraca procesor, gdy zakończy wykonywać kod funkcji. Ponieważ pamięć jest skończona, to nie można w niej umieścić nieskończenie wielu adresów powrotnych. Dlatego w rekurencji bardzo ważne jest określenie warunku, który kończy rekurencję - np. funkcja przestaje już dalej wywoływać samą siebie. |
||
Rekurencyjna silniaSilnia n! (ang. factorial of n) jest iloczynem kolejnych liczb naturalnych mniejszych lub równych n. Możemy ją zapisać w sposób rekurencyjny:
Wykorzystując ten wzór policzmy np. 5!:
Zwróć uwagę, iż w obliczeniach cofamy się od n = 5 do n = 0. Gdy osiągniemy 0, to rekurencja ustaje, ponieważ 0! jest dane bezpośrednio.
Silnia rośnie bardzo szybko. Już 13! przekroczy dopuszczalny zakres dla liczb typu unsigned (0...4mld). Zwróć uwagę, iż funkcja rekurencyjna jest bardzo prosta - to jest właśnie zaleta rekurencji.
|
||
Rekurencyjny Największy Wspólny DzielnikAlgorytm Euklidesa możemy również zapisać w sposób rekurencyjny:
Może się to wydawać na pierwszy rzut oka dziwne, lecz tak właśnie działa algorytm Euklidesa z dzieleniem, który omawialiśmy wcześniej. Traktuje on liczbę b jako resztę z dzielenia a przez b. Jeśli reszta z dzielenia jest równa 0, to kończy zwracając a. Jeśli nie, to a zastępuje przez b, czyli obecną resztą z dzielenia, a b zastępuje nową resztą z dzielenia i znów wykonuje sam siebie aż do pożądanego skutku.
(a) (b) → (b) (a mod b)
Zwróć uwagę, iż ponownie funkcja NWD uprościła się dzięki rekurencji.
|
||
Liczby FibonacciegoLiczby Fibonacciego powstają również rekurencyjnie:
Oto kilka początkowych liczb Fibonacciego:
Za wyjątkiem dwóch pierwszych, każda kolejna liczba Fibonacciego powstaje jako suma dwóch poprzednich liczb. Jeśli dla tych liczb zastosujemy metodę rekurencyjną, to, owszem, funkcja tworząca będzie prosta, lecz liczba wywołań rekurencyjnych może prześcignąć nasze wyobrażenia. Spróbujmy rozwinąć rekurencyjnie fib6 (na czerwono zaznaczono liczby Fibonacciego, które się dalej rozkładają rekurencyjnie):
fib6 = fib4
+ fib5
A teraz rozwinięcie rekurencyjne dla fib7:
fib7 = fib5
+ fib6 Jak widzimy, liczba wywołań lawinowo rośnie wraz ze wzrostem n. Taki przyrost nazywamy przyrostem wykładniczym. Niestety, ta cecha powoduje, iż obliczenie metodą rekurencyjną liczb Fibonacciego może być operacją bardzo czasochłonną dla dużych n.
Sprawdź działanie tego programu dla n = 40. Liczy parę sekund. Dla n = 50 możesz już stracić cierpliwość. A o wyliczeniu 90-tej liczby Fibonacciego zapomnij - człowiek tak długo nie żyje! Widzimy zatem, iż rekurencja może czasami prowadzić do algorytmów, których czas wykonania jest tak długi, że praktycznie algorytm nigdy się nie kończy. Tymczasem liczby Fibonacciego można wyliczać znacznie efektywniej, wykorzystując zasady tzw. programowania dynamicznego (ang. dynamic programming). W programowaniu dynamicznym algorytm wykorzystuje wyniki otrzymane w poprzednich krokach - obliczamy nową liczbę na podstawie dwóch poprzednich, a następnie zapamiętujemy dwie ostatnie liczby. Całość pracuje w pętli aż do wyznaczenia liczby Fibonacciego o pożądanym numerze.
Teraz program prawie natychmiast liczy wartość liczby fib90 = 2880067194370816120. Wersja rekurencyjna potrzebowałaby do tego wieków... |
||
ĆwiczeniaNapisz programy wypisujące n wyrazów poniższych ciągów:
|
 | I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe
