REKURENCJA - Podstawa wszystkich algorytmów



Rekurencja jest podstawą wszystkich algorytmów. Funkcja rekurencyjna jest to funkcja która wywołuje samą siebie np.
function Rekurencja:integer;
Begin
Rekurencja;
end;

Oczywiście po wywołaniu tej funkcji zapętliła by się ona w nieskończoność. Załóżmy że mamy pozbierać z podłogi zabawki :), zadanie to wydaje się łatwe do wykonania, jednak nie jest możliwe w jednej chwili pozbieranie wszystkich zabawek, najpierw weźmiemy jedną zabawkę i odłożymy ją na miejsce, następnie drugą itd. W ten sposób podzieliliśmy problem na wiele mniejszych, które są łatwe do wykonania. To działanie jest właśnie działaniem rekurencyjnym! Teraz może bardziej informatyczny przykład, mamy tablicę "tab" i chcemy znaleźć w niej liczbe "x". Postąpimy jak w poprzednim przykładzie, weźmiemy pierwszy element tablicy "tab[1]" i porównamy go z liczbą "x". Funkcja szukająca elementu "x" mogła by wyglądać tak :
const tab : array[1..6] of byte = (1,5,9,15,25,44); { tablica 6-cio
elementowa }

{ x - szukana liczba; ilElem - ilość elementów w tablicy;
Elem - numer aktualnie przeszukiwanego elementu,
przy wywołaniu oznacza numer elementu
od którego funkcja ma zacząć szukać.
funkcja zwraca numer szukanego elementu w tablicy,
lub gdy nie znajdzie go zwróci 0 }

function SzukajX(x, ilElem, Elem :byte) : byte;
Begin
if ( Elem > ilElem) then Result := 0 { sprawdza czy koniec tablicy }
else
if ( tab[Elem]=x ) then Result := Elem { porównuje element tablicy z "x" }
else
Result := SzukajX(x,ilElem, Elem + 1); { wywołuje samą siebie }
end;


Podany przykład nie wymaga omówienia, funkcja zwraca pozycję w tablicy, poszukiwanego elementu. Jeżeli będziesz miał jakieś problemy ze zrozumieniem tego przykładu, to najlepiej wklep go i uruchomić w trybie krokowym.
Niewątpliwą zaletą funkcji rekurencyjnych jest przejrzystość, kod jest krótki i łatwo znaleźć w nim ewentualne błędy. Wadami funkcji rekurencyjnych jest pamięciożerność, wielokrotne wywołanie funkcji może zająć większość zasobów systemowych.
Mam nadzieje że potrafisz już posługiwać się algorytmem rekurencyjnym i że będziesz posługiwał się nim w swoich programach.
W kolejnych tekstach opiszę kilka algorytmów bazujących na rekurencji.