Rekurencja i iteracja

Rekurencja

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, ma postać:

F_n= F_n-1 + F_n-2

F₀= 1 ; F₁ = 1

Oto podprogram w Pascalu, który wykonuje wywołanie rekurencyjne dla znajdowania n-tej wartości ciągu Fibonacciego:

function Fibonacci (n: integer) : integer;

begin

if n=0 then Fibonacci := 1;

if n=1 then Fibonacci := 1;

wynik := Fibonacci(n-1) + Fibonacci(n-2);

Fibonacci := wynik;

end;

Dwie pierwsze linie kodu funkcji są to tak zwane warunku brzegowe rekurencji. Kiedy rekurencja dotrze tak głęboko, że wiadomo, jaka jest wartość elementu ciągu Fibonacciego, należy zakończyć jej zagłębianie się. Gdyby nie te początkowe linie kodu rekurencja działałaby w nieskończoność, pobierając wartości Fibonacci(-1), Fibonacci(-2), co nie ma kompletnie sensu.

Dla znalezienia wartości trzeciej w ciągu Fibonacciego (F₂) algorytm zadziała następująco:

• n jest większe od jedynki, więc dwie pierwsze linijki się nie wykonają. Następnie zostanie wywołana procedura Fibonacci(1).

• Tutaj procedura zwróci już wynik 1, ponieważ wartość Fibonacci(1) jest równa jeden z definicji.

• Istotą rekurencji jest fakt, że teraz program wraca na wyższy poziom. Obliczył już pierwszą część sumy wyniku, teraz przejdzie do drugiej.

• I tutaj procedura zwróci wynik 1, jako że zostanie wywołana z parametrem 0.

• Znów nastąpi powrót z rekurencji. Obie wartości w wyniku zostały obliczone, teraz tylko je dodać i zwrócić wynik: 2.

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.

Iteracja

Iteracja (łac. iteratio) to czynność powtarzania (najczęściej wielokrotnego) tej samej instrukcji (albo wielu instrukcji) w pętli. Mianem iteracji określa się także operacje wykonywane wewnątrz takiej pętli. W odróżnieniu od rekurencji, która działa "od góry", iteracja do obliczenia n+1-szej wartości wykorzystuje poprzednią, n-tą iterację. Rekurencja dla obliczenia n-tej wartości potrzebowała zejścia aż do pierwszej wartości.

W większości języków programowania istnieje co najmniej kilka instrukcji iteracyjnych. Najważniejsze z nich to instrukcje FOR, WHILE i REPEAT (w języku C DO-WHILE).

FOR jest instrukcją, która liczy dokładnie ilość iteracji pętli. Jest to przydatne, kiedy wiemy, ile dokładnie wywołań iteracyjnych będzie nam potrzebnych. W języku Pascal instrukcja ta ma postać:

FOR zmienna := wartość-początkowa TO wartość-końcowa DO

Lub

FOR zmienna := wartość-końcowa DOWNTO wartość-początkowa DO

Przykład zastosowania pętli FOR to obliczanie silni.

function Silnia(n:Integer):Integer;

var i: Integer; wynik: Integer;

begin

wynik := 1;

for i:=2 to n do

wynik := wynik * i;

Silnia := wynik;

end;

WHILE jest instrukcją, która zapewnia wykonywanie się instrukcji wewnątrz pętli dopóki spełniony jest warunek logiczny.

Oto postać instrukcji WHILE w języku Pascal:

WHILE warunek DO …

Oto to samo obliczanie silni, tym razem z wykorzystaniem pętli WHILE:

function Silnia(n:Integer):Integer;

var i: Integer; wynik: Integer;

begin

wynik := 1;

i := 2;

while i<=n do

begin

wynik := wynik * i;

i := i+1;

end;

Silnia := wynik;

end;

Instrukcja REPEAT lub DO-WHILE jest używana dokładnie w takich samych wypadkach jak instrukcja WHILE, z tym, że warunek w niej podaje się na końcu, nie na początku pętli.

---