Rekurzia a vyhľadávanie

rekurzia

-rekurzívne procedúry a funkcie
-priama rekurzia - keď procedúra alebo funkcia v tele volá samú seba
-nepriama rekurzia - keď procedúra A volá procedúru B a tá zas procedúru A
-musíme zabezpečiť, aby volanie po konečnom počte skončilo - procedúra alebo funkcia musí mať nerekurzívnu vetvu:
napr.: rekurzívny program na výpočet n!
n! = n.(n-1)! ... rekurzívny vzťah
function fakt (n:integer):integer;
Begin
if n=0 then fakt:=1
else fakt:=n*fakt(n-1);
End;

vyhľadávanie

-budeme robiť nad zložkami typu pole
-pod vyhľadávaním rozumieme proces prezerania zložiek poľa s cieľom zistiť či pole obsahuje zložku s danými vlastnosťami; ak takúto zložku pole obsahuje, môže nás zaujímať jej miesto v poli - index
-poznáme 2 najznámejšie spôsoby vyhľadávania - lineárne (sekvenčné) a binárne
-vyhľadávanie v neutriedenej postupnosti
-ide zaradom, kým nenájdem prvok, ktorý hľadám a skončím vyhľadávanie
-ide zaradom až do konca a vypíše, kde sa prvok nachádza
-ide zaradom až do konca a vypíše počet prvkov s hľadanou vlastnosťou a ich indexy
-vyhľadávanie v utriedenej postupnosti
-tak ako pri vyhľadávaní v neutriedenej postupnosti
-zistím max. člen a zistím, či je väčší alebo menší ako moja hodnota
-binárnym vyhľadávaním - metóda delenia intervalu; vždy rozdelí postupnosť na 2 polovice a zistí v ktorej polovici sa hľadaná hodnota nachádza; opakujem, kým spodná a horná hranica nie sú rovnaké
-binárne triedenie: dolná + horná (trunc; round) : 2 (1 ... 100 = (1+100):2)