Informatyka dla klas II – rekurencja

Rekurencja

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 silnia

Silnia n! (ang. factorial of n) jest iloczynem kolejnych liczb naturalnych mniejszych lub równych n. Możemy ją zapisać w sposób rekurencyjny:

 

obrazek

 

Wykorzystując ten wzór policzmy np. 5!:

 

obrazek

 

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.

 

// Rekurencyjne wyznaczanie silni
// (C)2013 I LO w Tarnowie
//------------------------

 

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 Dzielnik

Algorytm Euklidesa możemy również zapisać w sposób rekurencyjny:

 

obrazek

 

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)

 

// Rekurencyjne obliczanie NWD
// (C)2013 I LO w Tarnowie
//------------------------

 

Zwróć uwagę, iż ponownie funkcja NWD uprościła się dzięki rekurencji.

 

Liczby Fibonacciego

Liczby Fibonacciego powstają również rekurencyjnie:

 

obrazek

 

Oto kilka początkowych liczb Fibonacciego:

 

obrazek

 

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
fib6 = fib2 + fib3 + fib3 + fib4
fib6 = fib0 + fib1 + fib1 + fib2 + fib1 + fib2 + fib2 + fib3
fib6 = fib0 + fib1 + fib1 + fib0 + fib1 + fib1 + fib0 + fib1 + fib0 + fib1 + fib1 + fib2
fib6 = fib0 + fib1 + fib1 + fib0 + fib1 + fib1 + fib0 + fib1 + fib0 + fib1 + fib1 + fib0 + fib1

 

A teraz rozwinięcie rekurencyjne dla fib7:

 

fib7 = fib5 + fib6
fib7 = fib3 + fib4 + fib4 + fib5
fib7 = fib1 + fib2 + fib2 + fib3 + fib2 + fib3 + fib3 + fib4
fib7 = fib1 + fib0 + fib1 + fib0 + fib1 + fib1 + fib2 + fib0 + fib1 + fib1 + fib2 + fib1 + fib2 + fib2 + fib3
fib7 = fib1 + fib0 + fib1 + fib0 + fib1 + fib1 + fib0 + fib1 + fib0 + fib1 + fib1 + fib0 + fib1 + fib1 + fib0 + fib1 + fib0 + fib1 + fib1 + fib2
fib7 = fib1 + fib0 + fib1 + fib0 + fib1 + fib1 + fib0 + fib1 + fib0 + fib1 + fib1 + fib0 + fib1 + fib1 + fib0 + fib1 + fib0 + fib1 + fib1 + fib0 + fib1

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.

 

// Rekurencyjne obliczanie liczb Fibonacciego
// (C)2013 I LO w Tarnowie
//------------------------

 

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.

 

// Dynamiczne obliczanie liczb Fibonacciego
// (C)2013 I LO w Tarnowie
//------------------------

 

Teraz program prawie natychmiast liczy wartość liczby fib90  = 2880067194370816120. Wersja rekurencyjna potrzebowałaby do tego wieków...

Ćwiczenia

Napisz programy wypisujące n wyrazów poniższych ciągów:

a) obrazek
b)obrazek

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2024 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

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