Rekurzia

Podprogramy

Vieme, že z podprogramu môžme volať len tie podprogramy, ktoré sú z miesta volania viditeľné. Volať možno "svoje deti" a starších bratov a tiež každý podprogram môže volať sám seba. Práve volanie seba má špeciálne využitie a nazývame to "rekurzia".
Opakovanie pojmov

Procedúry

blok programu, ktorý možno samostatne ladiť - pre každú množinu vstupných dát vieme určiť ako má vyzerať množina výstupných dát. Nemá návratovú hodnotu, v programe volanie procedúry je samostatný príkaz.

Funkcie

blok programu, ktorý možno samostatne ladiť - pre každú množinu vstupných dát vieme určiť ako má vyzerať množina výstupných dát (obyčajne len jedna hodnota). Má návratovú hodnotu, v programe volanie funkcie je časťou výrazu. V tele funkcie musí byť menu funkcie aspoň raz priradená nejaká hodnota - návratová hodnota funkcie.

Parametre volané hodnotou - vstupné

V zásobníku sa vytvorí premenná a do nej sa nakopíruje hodnota parametra pri volaní. Pre veľké štruktúry (polia) nevhodný postup lebo sa zaberá veľa pamäti v zásobníku a presun veľkého množstva dát trvá dlho. Môžu prenášať hodnoty z hlavného programu do podprogramu - skutočné parametre z hlavného programu sa pri volaní nezmenia.

Parametre volané menom - vstupno-výstupné

Podprogram pracuje s premennou hlavného programu priamo a teda zmenou hodnoty takéhoto parametra sa zmení aj hodnota parametra-premennej z volania v hlavnom programe.

Lokálne premenné

viditelnosť
životnosť
umiestnenie - zásobník

Rekurzia je podobná cyklu (tiež sa budú príkazy opakovať), ale sú niektoré dôležité rozdiely:

Každé volanie podprogramu (a teda aj volanie samo seba) vytvorí nové lokálne premenné. Každý beh rekurzie je teda pamäťovo náročný - do zásobníka sa uloží
- návratová adresa
- lokálne premenné včítane parametrov
Cyklus može teoreticky zbehnúť neobmedzený počet krát - rekurzia vždy narazí na hranicu určenú veľkosťou zásobníka (v Pascale max. 64kB) po prekročení ktorého nastane error "Stack overflow"
každý cyklus jednoducho možno nahradiť rekurziou no nahradenie rekurzie je úloha niekedy dosť obtiažna

Nekonečná rekurzia

procedúra pridaj volá samu seba:

program Rek;
var
  dlzka:integer;
  
  procedure pridaj(n:byte);
  s: string;
  i:integer;
  begin
    s:='';
	for i:= 1 to n do s:=s+chr(97+random(26));
    writeln(s); 	
    pridaj(10+random(10));
  end;

begin
  pridaj(10);
end;

Úlohou procedúry je vypisovať náhodné slová tvorené malými anglickými písmenami o dĺžke 10 až 19 znakov. Každé volanie zapíše do zásobníka
- návratovú adresu 16-bitov
- stringovú premennú s (náhodná hodnota)
- integerovú premennú i (náhodná hodnota)
- bajtovú premennú n (hodnota podľa hodnoty pri volaní) a nakoniec teda narazí na strop zásobníka a spadne s chybou "Pretečenie zásobníka". Nekonečná rekurzia teda nemá v programovaní význam lebo vedie zaručene ku pádu programu.

Dôsledok: Každý správny rekurzívny podprogram má "nerekurzívnu" vetvu - vetvu, kde sa nenachádza volanie sama seba. Ináč povedané:
"každý správny rekurzívny podprogram musí mať šancu nevolať sám seba".

Jednoduchá - chvostová rekurzia

Chvostová rekurzia nastane vtedy, keď rekurzívna procedúra volá samu seba ako posledný svoj príkaz. Takáto rekurzia sa veľmi ľahko dá prepísať na cyklus. Jej použitie je iba na cvičné účely.

Rekurzívna verzia

Rekurzívna verzia
`Program vypocet; Function faktorial(n: byte):longint; Begin if n=0 then faktorial=1 else faktorial = n* faktorial(n-1); End; Begin writeln('Zadaj N: '); Readln(n); writeln('Faktorial =', faktorial(n)); End;`
Nerekurzívna verzia
`Program vypocet; Function faktorial(n: byte):longint; var i:byte; v:longint; Begin v:=1; for i:=1 to n do v:=v*i; faktorial:= v; End; Begin writeln('Zadaj N: '); Readln(n); writeln('Faktorial =', faktorial(n)); End;`


Program vypocet;
   Function faktorial(n: byte):longint;
   Begin
     if n=0 then faktorial=1
            else faktorial = n* faktorial(n-1);
   End;
Begin
   writeln('Zadaj N: '); Readln(n);
   writeln('Faktorial =', faktorial(n));
End;

Nerekurzívna verzia


Program vypocet;
   Function faktorial(n: byte):longint;
   var i:byte;
       v:longint;
   Begin
     v:=1;  
     for i:=1 to n do v:=v*i;
	 faktorial:= v;
   End;
Begin
   writeln('Zadaj N: '); Readln(n);
   writeln('Faktorial =', faktorial(n));
End;

Takáto rekurzia nemá zmysel lebo oproti iterácii je omnoho časovo náročnejšia i ťažšie laditelná ale pomôže nám pochopiť ako to prebieha "vnútri" rekurzie.

pohľad
Pri hľadaní rekurzívneho riešenia je často vhodná asociácia
"šéf" dostal za úlohu od nadriadeného vypočítať n faktoriál, ako šéf nemusí robiť ťažké úlohy (na to má lidi) tak sa najprv pozrie, či úloha nie je ľahká
- pri výpočte faktoriálu je určite ľahkou úlohou vypočítať 0! čo šéf promptne spraví a odošle nadriadenému.
- ak je parameter n>0 úloha by bola ľahká ak by šéf poznal (n-1)! potom n! = n*(n-1)! tak poverí svojho podriadeného výpočtom (n-1)!. Šéf už potom nepreveruje hodnotu, čo mu podriadený dodá (svojim ľuďom veríme )len urobí potrebný súčin a odošle výsledok.
Aby toto "šéfovanie" fungovalo musí byť splnené - každý podriadený musí dostať od svojho šéfa úlohu ľahšiu ako dostal on sám.
(Presne - konečný počet takýchto zľahčení musí doviesť úlohu na triviálnu, kde už podriadeného netreba)
pohľad
technický - každé volanie podprogramu vytvára svoje premenné v zásobníku, kedže podprogram je stále ten istý - premenné sa volajú rovnako ale to nevadí každý podprogram vidí len svoje premenné a nemôže zmeniť premenné inému podprogramu (aj keď sa volajú rovanako).

Rekurzia
`Program vypocet; uses crt; Procedure vstup; var z: char; Begin z:= readkey; write(z); if z <> '*' then vstup else writeln; write(z); End; Begin vstup; End;`

Ak na vstup zadáme JA*, program vypíše
JA*
*AJ
porozmýšľajte prečo v druhom riadku sú písmená poprehadzované.

Pravá rekurzia

Ak sa za rekurzívnym volaním nachádzajú ešte nejaké príkazy alebo ak rekurzívne voláme na viacerých miestach programu je prechod na nerekurzívny algoritmus zložitejší.
Typické úlohy riešené rekurzívne:

Rozdeľ a panuj

Ide o delenie úlohy nejakej zložitosti na 2 alebo viac podúloh menšej zložitosti.
Typickými úlohami sú napríklad:

Naplň bunky poľa "pole" indexu N1 ... N2 rovnakou hodnotou 1 bez použitia cyklu
Myšlienka je rozdeliť rozdeliť úsek o dĺžke N2-N1+1 na menšie úseky. Úloha je zložitosti N2-N1+1 a možno ju deliť na úlohu zložitosti 1 (úsek dĺžky 1) a N2-N1 alebo šikovnejšie je deliť zložitosť približne ma rovnako zložité úseky.

Naplnenie poľa
`Procedure plnenie(a,b:integer); var s:integer; Begin s:=(b+a) div 2; if (b-a)=0 then pole[a]:=1 else Begin plnenie (a, s); plnenie(s+1, b); End; End;`

Dôkaz správnosti algoritmu je cez matematickú indukciu.

Hanojské veže
Permutácia n prvkov
Súčet veľkého počtu reálnych čísel v poli

O deravej šachovnici

Daná je šachovnica rozmeru n.n, kde n je mocnina 2, t.j. n = 2^m, m je celé. Políčko šachovnice, ktoré má súradnice [x; y], je vystrihnuté, 1 . x; y . n. Napíšte program, ktorý zvyšok šachovnice rozstrihá na triminá tvaru L, čo je útvar zložený z troch štvorcov do tvaru L. Napríklad pre n = 8 (m = 3); dieru [x; y] = [1; 4] úloha má riešenie.
Zdrojak - klikni pravým s stiahni
Exe - klikni pravým s stiahni

1112. O súčte čísel
Na vstupe máme postupnosť prirodzených čísel ukončenú nulou. Napíšte program, ktorý načíta túto postupnosť a vypíše jej súčet.
Obmedzenie: V celom programe môžete použi» iba procedúry bez parametrov a jedinú jednoduchú globálnu premennú.

Prehladávanie s návratom

Tiež niekedy nazývaná metóda "pokus omyl". Ide o úlohy, keď je systém popísaný stavmi a prechodmi z ktorého stavu možno prejsť do ktorého. Našou úlohou býva zistiť či existuje prechod zo stavu A do stavu B.

Najznámejší príklad je klasické plošné bludisko, kde je úlohou nájsť miestnosť s nejakou vlastnosťou. Pohyb po bludisku pripomína dávny príbeh z minulosti Tezeus < -- > Minotaurus. Hrdina sa vyberie jednou z prístupných ciest, značí si kde už bol a keď sa nedá ísť ďalej vráti sa späť. Touto metódou zaručene prejdeme celé bludisko.
stiahni ver 1.0 ver 1.1 ver 1.2
Zistenie plochy najväčšieho ostrova na mape (mapa je napr. daná tabuľkou, kde voda je napr. '.' a pevnina 'X')
zistenie počtu ostrovov
Je daná mapa - každý štvorček mapy je zadaný nadmorskou výškou (zväčšenou o 1000 ak nie je zaliaty)
Napr. číslo 1005 hovorí že štvorček má nadm. výšku 5 m nad hladinou
číslo 900 hovorí že nadmorská výška je -100 ale nie je zatopený
číslo -5 hovorí, že nadmorská výška je -5 a je zatopený
zakreslite mapu ak more stúpne o N metrov
problém 8 dám na šachovnici

Rekuzívne obrázky

Veľmi pripomínajú úlohy Rozdeľ a panuj" ale ide o špecifické grafické úlohy a tak sa často uvádzajú samostatne.

Vytvorte program, ktorý kreslí nasledovné rekurzívne krivky. Vždy sú uvedené prvé tri úrovne.

Špeciálne úlohy

Bez poľa a bez stringu načítaj znaky ukončené znakom Enter (#13) a vypíšte ich odzadu
Riešenie diofantických úloh ax-by = 1, pre a,b>0 v obore Z₀⁺
(Nech a>b, a=b*q+r ->ax-by=(bq+r)x-by = rx -b(y-qx)=1
nech b>a, b=a*q+r ->ax-by=ax-(aq+r)y = a(x-qy)-ry=1
trivialne riešenia sú ak a*b=0 alebo (a-1)*(b-1)=0)
Majme danú postupnosť:
S₀ = '@'
S₁ = 'A'+S₀+'A'+S₀+'A'
...
S_i = X_i+S_i-1+X_i+S_i-1+X_i {X_i je i-te písmeno veľkej anglickej abecedy, 1< i > 27}
...
Zisti v postupnosti N-te písmeno (N...je longint) v texte S₂₆

Otázky

Čo je rekurzia
Prečo nemôže rekurzia vytvoriť nekonečnú smyčku
Ako by ste riešili úlohu Hanojských veží