Algorytmy i Programowanie - Ćwiczenia 5

Temat: Procedury i funkcje. Stałe. Rekurencja.

Procedury i funkcje

Procedury i funkcje to takie kawałki programów, które mogą być wywoływane z innych miejsc w programie dowolną liczbę razy. Czasem są nazywane po prostu podprogramami. Procedura i funkcja może operować na pewnych danych wejściowych. Różnica między nimi polega na tym, że funkcja zwraca pewną wartość, podczas gdy procedura nie. Procedurę definiuje się następująco:

procedure nazwa_procedury(nazwa_parametru_int: integer)
begin
  // kod procedury
end;

Funkcję definiuje się następująco:

function nazwa_funckji(nazwa_parametru_int: integer): integer // typ liczby, którą funkcja zwraca
begin
  // kod funkcji
  nazwa_funkcji := wartosc; // zwrócenie wyniku przez funkcję i zakończenie jej działania
end;

Przykład: funkcja obliczająca wartość bezwzględną argumentu typu integer

function wartosc_bezwzgledna(x: integer)
begin
if (x > 0) then wartosc_bezwzgledna := x
           else wartosc_bezwzgledna := (-1)*x;
end;

Zarówno do procedury jak i funkcji parametry mogą być przekazywane przez wartość lub przez referencję. W powyższym przykładzie parametr został przekazany przez wartosc. O przekazywaniu parametrów przez referencję będziemy szerzej mówic na zajeciach dotyczacych wskazników. Dla argumentów przekazanych przez wartość, wewnatrz funkcji jest tworzona ich lokalna kopia. Oznacza to, że zmiany dokonane na tych argumentach nie będą widoczne poza funkcją. W przypadku przekazania zmiennej przez referencję, zmiany wartości zmiennej będą widoczne także poza funkcją.

Stałe

W języku Pascal oprócz zmiennym, można także na początku programu definiować dowolne stałe. Robi się to przy pomocy polecenia const.
Przykład deklaracji i użycia stałych:

const PI = 3.14;

begin
  r := 4;
  pole_kola := r*r*PI; // Pod PI zostanie podstawione 3,14 i obliczone zostanie pole koła o promieniu r
end.

Rekurencja

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.
Funkcja rekurencyjna przeważnie opiera się na pewnym wzorze, w którym po obu stronach równości występuje ta sama funkcja obliczana dla różnej wielkości parametru. Oprócz tego w każdej funkcji rekurencyjnej niezbędny jest tzw. "warunek początkowy", dzięki któremu wartość funkcji można obliczyć.
Najłatwiej zrozumieć mechanizm działania rekursji na przykładzie silni.

Silnia

Matematyczna definicja silni wygląda następująco:

$n!=\begin{cases} 1 & \mbox{ dla }n=0 \\ n(n-1)! & \mbox{ dla }n\ge1 \end{cases}$
Jak widać, silnia zdefiniowana jest niemal przez samą siebie. Do tego mamy zdefiniowany warunek początkowy: 0! = 1;
Czyli aby obliczyć 4! trzeba najpierw obliczyć 3! i wynik pomnożyć przez 4. Żeby obliczyć 3! trzeba obliczyć 2!. Żeby z kolei to obliczyć trzeba znać 1!, do obliczenia którego jest potrzebne 0!, którą to liczbę znamy, bo jest nią 1. Zatem teraz cofając się z tym rozumowaniem i podstawiając kolejne wartości mamy:
1! = 1*1 = 1;
2! = 2*1! = 2*1 = 2; 3! = 3*2! = 3*2 = 6; 4! = 4*3! = 4*6 = 24;

Rekurencja c.d.

Funkcje rekurencyjną często można zamienić na zwykłą funkcję iteracyjną. Np. w przypadku silni oczywiście wiemy, że n! = n(n-1)(n-2)...2*1. Można to łatwo wyliczyć przy pomocy zwykłej pętli. I jeśli tylko można należy rekurencji unikać, gdyż funkcje rekurencyjne mają przeważnie dużą złożoność obliczeniową, a ponadto wymagają zastosowania wewnętrznego stosu.
Niemniej często nie da się zrobić czegoś bez rekurencji, więc jest to narzędzie bardzo przydatne, które warto znać.