Politechnika Świętokrzyska w Kielcach Wydział Elektrotechniki, Automatyki i Informatyki
Laboratorium Podstaw Programowania 2
Lab. nr 8
Data wykonania ćwiczenia : 27.04.2012
1.Przemysław Wolski

1. Wstęp teoretyczny.

Rekurencja jest techniką programowania, dzięki której procedura, funkcja lub podprogram jest w stanie w swoim ciele wywołać sam siebie. Trudno w to uwierzyć, ale niektóre "stare" języki programowania nie udostępniały możliwości wywołań rekurencyjnych.

Po co nam jest rekurencja? Przede wszystkim dzięki niej łatwo jest wykonać wiele zadań, w których potrzeba jest wyników cząstkowych do obliczenia całości. Sztandarowym przykładem w zagadnieniu rekurencji jest liczenie silni (n!), lub nieco bardziej zaawansowany przykład liczenia n-tej wartości w ciągu Fibonacciego.

Dla przypomnienia, ciąg Fibonacciego jest ciągiem, w którym każda następna wartość jest równa sumie dwóch poprzednich. Równanie rekurencyjne, na którym opiera się podprogram rekurencyjny

Rekurencja działa dzięki temu, że za każdym razem, kiedy jest wywoływana, do życia jest powoływany nowy zestaw zmiennych lokalnych, zaś stare odkładane są na bok, w specjalnej strukturze danych zwanej stosem. Dzięki za wszystko temu za każdym razem, kiedy program "wraca" z wywołań rekurencyjnych, może sięgnąć do dawnych wartości zmiennych i działać z nimi, przy okazji wiedząc dużo o innych wywołaniach rekurencyjnych samego siebie.

Istnieją problemy, które da się rozwiązać tylko dzięki rekurencji. Oczywiście można je zapisać iteracyjnie, jednak wówczas potrzebny jest nasz własny stos, o który będziemy sami dbali. Rekurencja ma tę ważną zaletę, że o wszystkim decyduje i o wszystko dba kompilator

2. Przebieg ćwiczenia.

Zadanie 1.

Napisać program, który będzie obliczał silnię.

Program należy napisać w 2 wersjach:

• wersja rekurencyjna;

• wersja iteracyjna

program lab8zad1a; uses crt; var n:integer; function silnia(n:integer):integer; begin if (n=0) or (n=1) then silnia:=1 else silnia:=n*silnia(n-1); end; begin clrscr; writeln('Podaj liczbe !'); readln(n); writeln(silnia(n)); readln; end.	N czyli liczba podawana przez użytkownika. Funkcja rekurencyjna obliczająca silnię z n Program główny

program lab8zad1b; uses crt; procedure sil; var a:integer; i:byte; n:longint; begin repeat writeln('Podaj liczbe '); readln(a); until (a>=0); n:=1; for i:=1 to a do n:=n*i; writeln(n); end; begin clrscr; sil; repeat until keypressed; end.	Procedura iteracyjna obliczająca silnię. Pobiera od użytkownika liczę (a). Za pomocą pętli for oblicza silnię Wypisuje wynik na ekranie. Program główny.

Zadanie 2.

Napisać program wyliczający kolejne wyrazy ciągu Fibonacciego. Jest to ciąg, w którym 2 pierwsze wyrazy to 0 i 1, a kolejne są sumą dwóch poprzednich wyrazów. Np.: 0 1 1 2 3 5 8 … itd.

Program należy napisać w 2 wersjach:

• wersja rekurencyjna;

• wersja iteracyjna.

Jako parametr program przyjmuje indeks wyrazu ciągu, który należy wyliczyć.

program lab8zad2a; uses crt; var n,wynik:integer; function fib(x:integer):integer; begin if (x=1) or (x=0) then fib:=x else if x>1 then fib:=fib(x-1)+fib(x-2); end; begin clrscr; writeln('Podaj wyraz ciagu ktory chcesz obliczyc !'); readln(n); wynik:=fib(n); writeln(wynik); repeat until keypressed; end.	Rekurencyjna funkcja obliczająca kolejne wyrazy ciągu Fibonacciego. Wywołuje się sama przez siebie odkładając aktualne wartości na bok. Program główny. Pobranie od użytkownika konkretnego wyrazu który chcielibyśmy zobaczyć. Wyświetlenie go.

program lab8zad2b; uses crt; procedure main; var m,n,b,i,liczba:integer; begin writeln('Podaj ktory wyraz ciagu Fibonacciego chcesz zobaczyc'); readln(liczba); m:=1; n:=1; if liczba=0 then writeln('0') else begin for i:=3 to liczba do begin b:=m+n; m:=n; n:=b; end; writeln(b); end; end; begin clrscr; main; readln; end.	Pobranie od użytkownika konkretnego wyrazu który chcielibyśmy zobaczyć. Wyświetlenie wyniku. Program główny.

Zadanie 3.

Wyznacz miejsca zerowe funkcji metodą bisekcji z dokładnością eps.

Program należy napisać w 2 wersjach:

• wersja rekurencyjna;

• wersja iteracyjna.

program lab8zad3; uses crt; function f(x:real):real; begin f:=(x*x-1); end; procedure glowny; var a,b,eps,c,wynik:real; begin write('Podaj a: '); readln(a); write('Podaj b: '); readln(b); write('Podaj eps: '); readln(eps); if (f(a)*f(b))>0 then writeln('Brak miejsc zerwoych ') else begin while abs(b-a)>eps do begin c:=(a+b)/2; if f(a)*f(c)<0 then b:=c else a:=c; end; wynik:=((a+b)/2); end; writeln('Miejsce zerowe: ',wynik:5:10); end; begin clrscr; glowny; readln; end.

Funkcja podstawiająca argument pod wzór funkcji. Wczytanie od użytkownika przedziału. Wczytanie dokładności. Komunikat w przypadku wczytania złych zmiennych. Ostateczny wynik. Wyświetlenie wyniku. Program główny.

3. Wnioski

Każdy problem mający rozwiązanie rekurencyjne daje się także rozwiązać w sposób iteracyjny, choć jego rozwiązanie iteracyjne może być mniej czytelne w porównaniu z rekurencyjnym, a niekiedy wręcz sztuczne.

Rekurencja może być ponadto symulowana w sposób iteracyjny, przy użyciu struktur danych zwanych stosami (patrz dalsze wykłady).

Istnieje powszechne przekonanie że nauczenie się programowania iteracyjnego czy też stosowania nie rekurencyjnych wywołań funkcji jest łatwiejsze niż nauczenie się programowania rekurencyjnego.

Po zdobyciu odpowiedniego doświadczenia, często okazuje się że programowanie rekurencyjne jest równie łatwe.

Programy rekurencyjne są często mniejsze i łatwiejsze do zrozumienia od ich iteracyjnych odpowiedników.

Co ważniejsze, niektóre problemy (szczególnie niektóre problemy wyszukiwania) są znacznie łatwiejsze do rozwiązania za pomocą programów rekurencyjnych.