1 Algorytmy rekurencyjne - przykładProblem: tablica n liczb całkowitych tab[n]=tab[0], tab[1], …, tab[n-1]; czy w tablicy tab występuje liczba x (podana jako parametr)? Rozumowanie: wziąć pierwszy niezbadany element tablicy n-elementowej; jeśli aktualnie analizowany element tablicy jest równy x, to: wypisz „Sukces” i zakończ; w przeciwnym wypadku: zbadaj pozostałą część tablicy n-1 elementowej. Gdy przebadaliśmy całą tablicę i element nie został znaleziony, można np. wyświetlić komunikat o niepowodzeniu.

2 Algorytmy rekurencyjne - przykładPrzykładowa realizacja: int const n=10; int tab[n]={1,2,3,2,-7,44,5,1,0,-3}; void szukaj(int tab[n], int left, int right, int x) //left, right - lewa i prawa granica obszaru poszukiwań //tab tablica //x wartość do odnalezienia { if (left>right) cout << "Element " << x << " nie został odnaleziony\n"; else if (tab[left]==x) cout <<"Znalazłem szukany element "<< x < szukaj(tab, left+1,right,x); }

3 Algorytmy rekurencyjne - cechyProgram ilustruje podstawowe cechy typowego programu rekurencyjnego: Zakończenie programu jest jasno określone element znaleziony przekroczenie zakresu tablicy Duży problem zostaje rozbity na problemy elementarne, które umiemy rozwiązać i na analogiczny problem, tylko o mniejszym stopniu skomplikowaniu z tablicy o rozmiarze n schodzimy do tablicy o rozmiarze n-1

4 Algorytmy rekurencyjne - podstawowe błędyzłe określenie warunku zakończenia programu niewłaściwa (nieefektywna) dekompozycja problemu

5 Algorytmy rekurencyjne - jak się wykonują?Przykład: Obliczanie silni unsigned long int silnia (int x) { if (x==0) return 1; else return x*silnia(x-1); } Proces przekazywania wyniku cząstkowego z poziomu niższego na wyższy Jak się liczy 3! Zagłębianie się programu z poziomu n na n-1 w celu dotarcia do przypadku elementarnego 0! Obliczanie wyników cząstkowych

6 Algorytmy rekurencyjne - niebezpieczeństwaPrzykład: Ciąg Fibonacciego. (Elementy tego ciągu stanowią liczby naturalne takie, że kolejny wyraz (z wyjątkiem dwóch pierwszych) jest sumą dwóch poprzednich, tj. 1, 1, 2, 3, 5, 8, 13,…) unsigned long int Fibonaci(int n) { if(n<2) return n else return Fibonaci(n-1)+Fibonaci(n-2); } Obliczanie czwartego elementu ciągu Znaczna część obliczeń jest wykonywana więcej niż jeden raz!! Każde zacieniowane wyrażenie stanowi problem elementarny

7 Algorytmy rekurencyjne - niebezpieczeństwaProgramy rekurencyjne są zazwyczaj dość pamięciożerne. Program obliczający 3! wywoła sam siebie tylko 3 razy, ale Fibonacci już nie jest taki łatwy do analizy. Przykład unsigned long int funkcja(int x) { if(x>100) return (x-10); else return funkcja(funkcja(x+11)); } Ile wywołań? Co się dzieje na większym przedziale liczbowym niż na rysunku? –ćw.

8 Algorytmy rekurencyjne - niebezpieczeństwaStack overflow, czyli funkcja Ackermanna #include int A(int n,int p) { if (n==0) return 1; if ((p==0)&&(n>=1)) if (n==1)return 2; else return n+2; if ((p>=1)&&(n>=1)) return A(A(n-1,p),p-1); } int main() cout << "A(3,4)="< Jaki jest powód komunikatu: „Stack overflow!” (przepełnienie stosu) podczas próby jego wykonania? Nastąpiła znaczna ilość wywołań funkcji Ackermanna.

9 Algorytmy rekurencyjne - niebezpieczeństwaStack overflow, czyli funkcja Ackermanna Analiza wywołań Pobieżna analiza funkcji A prowadzi do spostrzeżenia: Analogicznie dla 2 otrzymamy: Z samej definicji funkcji Ackermanna możemy wywnioskować, że Na bazie tych równań możliwe jest rekurencyjne udowodnienie, że

10 Algorytmy rekurencyjne - niebezpieczeństwaStack overflow, czyli funkcja Ackermanna Analiza wywołań Nieco gorsza jest sytuacja dla A(n,4), bo trudno jest podać wzór ogólny. Ale można zobaczyć przykłady liczbowe:

11 Algorytmy rekurencyjne - niebezpieczeństwaBłąd programisty! Sprowokowanie nieskończonej ilości wywołań rekurencyjnych! Przykład: int niesk(int n) { if(n==1) return 1; else if ((n%2)==0) //czy n jest parzyste? return niesk(n-2)*n; return niesk(n-1)*n; } Dla n>=2 wszystkie wywołania rekurencyjne kończą się parzystą liczbą n. Zatem dojdziemy do n=2, potem n=0, n=-2,…… Nigdzie po drodze nie ma przypadku elementarnego!

12 Algorytmy rekurencyjne - niebezpieczeństwaBłąd programisty! Jak go uniknąć? Sprawdzić matematycznie poprawność definicji rekurencyjnej, tzn. określić dziedziny wartości funkcji, udowodnić, że się ona zakończy, podać złożoność obliczeniową To nie wystarczy! Nie wiadomo, jak rzeczywisty kompilator wykona tę funkcję. int N(int n, int p) { if(n==0) return 1; else return N(n-1,N(n-p,p)); } Można udowodnić matematycznie, że powyższa definicja jest poprawna w tym sensie, że dla dowolnych n>=0, p>=0 jej wynik jest określony i wynosi 1. Zakłada się, że wartość argumentu wywołania funkcji jest obliczana tylko wtedy, gdy jest to konieczne. Jak wykona to typowy kompilator C++? Wszystkie parametry funkcji rekurencyjnej są obliczane jako pierwsze, a potem wywołana jest funkcja – wywołanie przez wartość.

13 Algorytmy rekurencyjne - niebezpieczeństwaZapętlenie jest spowodowane próbą obliczenia parametru p, tymczasem to drugie wywołanie nie jest potrzebne do zakończenia funkcji! Kompilator tego nie wie! int N(int n, int p) { if(n==0) return 1; else return N(n-1,N(n-p,p)); } Wszystkie parametry funkcji rekurencyjnej są obliczane jako pierwsze, a potem wywołana jest funkcja – wywołanie przez wartość.

14 Algorytmy rekurencyjne - zaletyŁatwe do zrozumienia Zajmują mało miejsca (liczba wierszy kodu) – ewentualnie łatwo znaleźć błędy Jak w takim razie usunąć wady? Inaczej zbudować rekurencję. Rekurencja „z parametrem dodatkowym” Rekurencja „naturalna” –poprzednie przykłady Na czym polega?

15 Algorytmy rekurencyjne - zaletyParametry domyślne funkcji fun(int a, int k=1) unsigned long int silnia (int x) { if (x==0) return 1; else return x*silnia(x-1); } Funkcja może być wywołana na dwa sposoby: Poprzez określenie wartości drugiego parametru, np. fun(2,5), wtedy k przyjmuje wartość 5; Bez określania wartości drugiego parametru, np. fun(12), wtedy k przyjmuje wartość domyślną równą tej podanej w nagłówku, czyli 1. unsigned long int silnia2 (int x, int tmp=1) { if (x==0) return tmp; else return silnia2(x-1,x*tmp); } Parametr dodatkowy przekazuje elementy wyniku końcowego – program nie ma potrzeby przekazywania wyniku obliczeń do góry, piętro po piętrze – ostatni aktywny poziom dostarczy wynik!

16 Algorytmy rekurencyjne - strategia „dziel izwyciężaj”

17 Algorytmy rekurencyjne - strategia „dziel izwyciężaj”

18 Algorytmy rekurencyjne - strategia „dziel izwyciężaj”Twierdzenie o rekurencji uniwersalnej podaje metodę rozwiązania tego typu rekurencji.

19 Algorytmy rekurencyjne - strategia „dziel izwyciężaj”

20 Sortowanie przez scalanie

21 Sortowanie przez scalanieZapis tego algorytmu w pseudokodzie:

22 Sortowanie przez scalanieWywołania rekurencyjne Ćwiczenie: Zapisać w C++

23 Sortowanie przez scalanieTwierdzenie:

24 Sortowanie przez scalanie

25 Sortowanie przez scalanie

26 Sortowanie przez scalanieKomentarz:

27 Sortowanie przez scalanieTwierdzenie:

28 Sortowanie przez scalanie

29 Sortowanie przez scalanieGdy n jest dowolną liczbą naturalną rozwiązanie rekurencji jest trudniejsze. Należy wykorzystać następujący wzór sumacyjny: Twierdzenie:

30 Sortowanie przez scalanieDowód:

31 Sortowanie przez scalanieDowód:

32 Sortowanie przez scalanie

33 Sortowanie przez scalanieKorzystając z podanego wcześniej wzoru sumacyjnego, możemy policzyć wartość sumy: co daje ostatecznie: